# zbMATH — the first resource for mathematics

On the metric dimension of line graphs. (English) Zbl 1262.05069
Summary: Let $$G$$ be a (di)graph. A set $$W$$ of vertices in $$G$$ is a 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 metric dimension $$\mu (G)$$ of $$G$$ is the minimum cardinality of all the resolving sets of $$G$$. In this paper we study the metric dimension of the line graph $$L(G)$$ of $$G$$. In particular, we show that $$\mu (L(G))=|E(G)|-|V(G)|$$ for a strongly connected digraph $$G$$ which is not a directed cycle, where $$V(G)$$ is the vertex set and $$E(G)$$ is the edge set of $$G$$. As a corollary, the metric dimension of de Bruijn digraphs and Kautz digraphs is given. Moreover, we prove that $$\lceil \log 2\Delta (G)\rceil \leq \mu (L(G))\leq |V(G)|-2$$ for a simple connected graph $$G$$ with at least five vertices, where $$\Delta (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.

##### MSC:
 05C20 Directed graphs (digraphs), tournaments 05C35 Extremal problems in graph theory 05C76 Graph operations (line graphs, products, etc.)
Full Text: