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

Authors

  • Douglas J Klein Texas A&M University at Galveston
  • Eunjeong Yi Texas A&M University at Galveston

Keywords:

line graph, para-line graph, line graph of the subdivision graph, distance, resolving set, metric dimension

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.

Downloads

Published

2012-07-31

Issue

Section

Discrete Mathematics

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