کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419399 | 683798 | 2013 | 4 صفحه PDF | دانلود رایگان |
Let GG be a (di)graph. A set WW of vertices in GG is a resolving set of GG if every vertex uu of GG is uniquely determined by its vector of distances to all the vertices in WW. The metric dimension μ(G)μ(G) of GG is the minimum cardinality of all the resolving sets of GG. In this paper we study the metric dimension of the line graph L(G)L(G) of GG. In particular, we show that μ(L(G))=|E(G)|−|V(G)|μ(L(G))=|E(G)|−|V(G)| for a strongly connected digraph GG 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 GG. 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⌈log2Δ(G)⌉≤μ(L(G))≤|V(G)|−2 for a simple connected graph GG with at least five vertices, where Δ(G)Δ(G) is the maximum degree of GG. Finally, we obtain the metric dimension of the line graph of a tree in terms of its parameters.
Journal: Discrete Applied Mathematics - Volume 161, Issue 6, April 2013, Pages 802–805