A comparison on metric dimension of graphs, line graphs, and line graphs of the subdivision graphs

Abstract

The line graph L(G) of a simple graph G is the graph whose vertices are in one-to-one correspondence with the edges of G; two vertices of L(G) are adjacent if and only if the corresponding edges of G are adjacent. If S(G) is the subdivision graph of a graph G, then the para-line graph $G^star$ of G is L(S(G)). The metric dimension dim(G) of a graph G is the minimum cardinality of a set of vertices such that every vertex of G is uniquely determined by its vector of distances to the chosen vertices. In this paper, we study metric dimension of para-line graphs; we also compare metric dimension of graphs, line graphs, and para-line graphs. First, we show that ⌈$log_2bigtriangleup$(G)⌉ ≤ dim($G^star$) ≤ n − 1, for a simple and connected graph G of order n ≥ 2 with the maximum degree $bigtriangleup$(G), where both bounds are sharp. Second, we determine the metric dimension of para-line graphs for some classes of graphs; further, we give an example of a graph G such that max{dim(G), dim(L(G)), dim($G^star$)} equals dim(G), dim(L(G)), and dim($G^star$), respectively. We conclude this paper with some open problems.