A Comparison on Metric Dimension of Graphs, Line Graphs, and Line Graphs of the Subdivision Graphs (European Journal of Pure and Applied Mathematics, 2012)
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^*$ of $G$ is $L(S(G))$. The metric dimension $\dim(G)$ of a graph $G$ is the minimum number of vertices such that all vertices are uniquely determined by their 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 $\lceil \log_2 Δ(G) \rceil \le Â \dim(G^{\star}) \le n-1$, for a simple and connected graph $G$ of order $n \ge 2$ with the maximum degree $Δ(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.