A Comparison on Metric Dimension of Graphs, Line Graphs, and Line Graphs of the Subdivision Graphs
Keywords:
line graph, para-line graph, line graph of the subdivision graph, distance, resolving set, metric dimensionAbstract
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.Downloads
Published
2012-07-31
Issue
Section
Discrete Mathematics
License
Upon acceptance of an article by the journal, the author(s) accept(s) the transfer of copyright of the article to European Journal of Pure and Applied Mathematics.
European Journal of Pure and Applied Mathematics will be Copyright Holder.
How to Cite
A Comparison on Metric Dimension of Graphs, Line Graphs, and Line Graphs of the Subdivision Graphs. (2012). European Journal of Pure and Applied Mathematics, 5(3), 302-316. https://www.ejpam.com/index.php/ejpam/article/view/1506