A Comparison on Metric Dimension of Graphs, Line Graphs, and Line Graphs of the Subdivision Graphs

Abstract

The \emph{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 \emph{subdivision graph} of a graph $G$, then the \emph{para-line graph} $G^*$ of $G$ is $L(S(G))$. The \emph{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 \Delta(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 $\Delta(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.