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.

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