On the metric dimension of line graphs
Let G G be a (di)graph. A set W W of vertices in G G is a resolving set  of G G if every vertex u u of G G is uniquely determined by its vector of distances to all the vertices in W W . The metric dimension ?(G) ? ( G ) of G G is the minimum cardinality of all the resolving sets of G G . In this paper we study the metric dimension of the line graph L(G) L ( G ) of G G . In particular, we show that ?(L(G))=|E(G)|?|V(G)| ? ( L ( G ) ) = | E ( G ) | ? | V ( G ) | for a strongly connected digraph G G which is not a directed cycle, where V(G) V ( G ) is the vertex set and E(G) E ( G ) is the edge set of G G . As a corollary, the metric dimension of de Bruijn digraphs and Kautz digraphs is given. Moreover, we prove that ?log2?(G)???(L(G))?|V(G)|?2 ? log 2 ? ( G ) ? ? ? ( L ( G ) ) ? | V ( G ) | ? 2 for a simple connected graph G G with at least five vertices, where ?(G) ? ( G ) is the maximum degree of G G . Finally, we obtain the metric dimension of the line graph of a tree in terms of its parameters.
metric dimension line graph resolving set de bruijn digraph kautz digraph