On the metric dimension of line graphs

Abstract

Let $G$ be a (di)graph. A set $W$ of vertices in $G$ is a \emph{resolving set} of $G$ if every vertex $u$ of $G$ is uniquely determined by its vector of distances to all the vertices in $W$. The \emph{metric dimension} $\hat{I}¼(G)$ of $G$ is the minimum cardinality of all the resolving sets of $G$. Cáceres et al. \cite{Ca2} computed the metric dimension of the line graphs of complete bipartite graphs. Recently, Bailey and Cameron \cite{Ba} computed the metric dimension of the line graphs of complete graphs. In this paper we study the metric dimension of the line graph $L(G)$ of $G$. In particular, we show that $\hat{I}¼(L(G))=|E(G)|-|V(G)|$ for a strongly connected digraph $G$ except for directed cycles, where $V(G)$ is the vertex set and $E(G)$ is the edge set of $G$. As a corollary, the metric dimension of de Brujin digraphs and Kautz digraphs is given. Moreover, we prove that $\lceil {\log }_2\hat{I}”(G)\rceil \le \hat{I}¼(L(G))\le |V(G)|-2$ for a simple connected graph $G$ with at least five vertices, where $\hat{I}”(G)$ is the maximum degree of $G$. Finally, we obtain the metric dimension of the line graph of a tree in terms of its parameters.

7 pages