Klein, Douglas J.; Yi, Eunjeong A comparison on metric dimension of graphs, line graphs, and line graphs of the subdivision graphs. (English) Zbl 1389.05031 Eur. J. Pure Appl. Math. 5, No. 3, 302-316 (2012). Summary: 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 \Delta(G) \rceil \leq ~\dim(G^{\star}) \leq n-1\), for a simple and connected graph \(G\) of order \(n \geq 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. Cited in 12 Documents MSC: 05C12 Distance in graphs 05C76 Graph operations (line graphs, products, etc.) Keywords:line graph; para-line graph; line graph of the subdivision graph; distance; resolving set; metric dimension PDFBibTeX XMLCite \textit{D. J. Klein} and \textit{E. Yi}, Eur. J. Pure Appl. Math. 5, No. 3, 302--316 (2012; Zbl 1389.05031) Full Text: Link References: [1] R.F. Bailey and P.J. Cameron. Base size, metric dimension and other invariants of groups and graphs. Bulletin of the London Mathematical Society.43(2), 209-242. 2011. · Zbl 1220.05030 [2] L.W. Beineke. Characterizations of Derived Graphs. Journal of Combinatorial Theory. 9, 129-135. 1970. · Zbl 0202.55702 [3] P.S. Buczkowski, G. Chartrand, C. Poisson, and P. Zhang. On k-dimensional graphs and their bases. Periodica Mathematica Hungarica.46(1), 9-15. 2003. · Zbl 1026.05033 [4] J. Cáceres, C. Hernado, M. Mora, I.M. Pelayo, M.L. Puertas, C. Seara, and D.R. Wood. On the Metric Dimension of Cartesian Products of Graphs. SIAM Journal on Discrete Mathematics.21, Issue 2, 423-441. 2007. · Zbl 1139.05314 [5] G. Chartrand, L. Eroh, M.A. Johnson, O.R. Oellermann. Resolvability in graphs and the metric dimension of a graph. Discrete Applied Mathematics.105, 99-113. 2000. · Zbl 0958.05042 [6] G. Chartrand and P. Zhang. Introduction to Graph Theory. McGraw-Hill, Kalamazoo, MI. 2004. [7] G. Chartrand and P. Zhang. The theory and applications of resolvability in graphs. A Survey. Congressus Numerantium.160, 47-68. 2003. REFERENCES315 [8] L. Eroh, C.X. Kang, and E. Yi. A Comparison between the Metric Dimension and Zero Forcing Number of Line Graphs. arXiv:1207.6127v1. · Zbl 1340.05057 [9] L. Eroh, C.X. Kang, and E. Yi. On Metric Dimension of Graphs and Their Complements. Journal of Combinatorial Mathematics and Combinatorial Computing. to appear. · Zbl 1270.05036 [10] M. Feng, M. Xu, and K. Wang. On the metric dimension of line graphs. arXiv:1107.4140v1. · Zbl 1262.05069 [11] K. Fukui, H. Kato, and T. Yonezawa. A New Quantum-mechanical Reactivity Index for Saturated Compounds. Bulletin of the Chemical Society of Japan.34, 1111-1115. 1961. [12] M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York. 1979. · Zbl 0411.68039 [13] F. Harary and R.A. Melter. On the metric dimension of a graph. Ars Combinatoria. 2, 191-195. 1976. · Zbl 0349.05118 [14] C. Hernando, M. Mora, I.M. Pelayo, C. Seara, and D.R. Wood. Extremal Graph Theory for Metric Dimension and Diameter. Electronic Journal of Combinatorics.17 (1), #R30. 2010. · Zbl 1219.05051 [15] Y. Higuchi and T. Shirai. Some Spectral and Geometric Properties for Infinite Graphs. Discrete geometric analysis, Contemporary Mathematics.347, 29-56. American Mathematical Society, Providence, RI. 2004. · Zbl 1079.47035 [16] H. Iswadi, E.T. Baskoro, A.N.M. Salman, and R. Simanjuntak. The Metric Dimension of Amalgamation of Cycles. Far East Journal of Mathematical Sciences.41, Number 1, 19-31. 2010. · Zbl 1194.05033 [17] S. Khuller, B. Raghavachari, and A. Rosenfeld. Landmarks in Graphs. Discrete Applied Mathematics.70, 217-229. 1996. · Zbl 0865.68090 [18] J. Krausz. Demonstration nouvelle d’une Théorème de Whitney sur les Réseaux. Mat. Fiz. Lapok50, 75-85. 1943. · Zbl 0061.41401 [19] C. Poisson and P. Zhang. The Metric Dimension of Unicyclic Graphs. Journal of Combi- natorial Mathematics and Combinatorial Computing.40, 17-32. 2002. · Zbl 0990.05040 [20] J.A. Pople and D.P. Santry. A molecular orbital theory of hydrocarbons. Molecular Physics. 7 Issue 3, 269-286. 1964. [21] P.S. Ranjini, V. Lokesha, and I.N. Cangül. On the Zagreb indices of the line graphs of the subdivision graphs. Applied Mathematics and Computation.218, Issue 3, 699-702. 2011. · Zbl 1233.05092 [22] C. Sandorfy. LCAO MO Calculations on Saturated Hydrocarbons and Their Substituted Derivatives. Canadian Journal of Chemistry.33, 1337-1351. 1955. REFERENCES316 [23] A. Sebö and E. Tannier. On metric generators of graphs. Mathematics of Operations Re- search.29, 383-393. 2004. · Zbl 1082.05032 [24] B. Shanmukha, B. Sooryanarayana, and K.S. Harinath. Metric dimension of wheels. Far East Journal of Applied Mathematics.8 (3), 217-229. 2002. · Zbl 1032.05044 [25] T. Shiraithe. Spectrum of Infinite Regular Line Graphs. Transactions of the American Mathematical Society.352, Number 1, 115-132. 1999. [26] P.J. Slater. Dominating and reference sets in a graph. Journal of Mathematical and Phys- ical Sciences.22, 445-455. 1998. · Zbl 0656.05057 [27] P.J. Slater. Leaves of trees. Congressus Numerantium. 14, 549-559. 1975. [28] A. van Rooij and H. Wilf. The Interchange Graph of a Finite Graph. Acta Mathematica Academiae Scientiarum Hungaricae.16, 263-269. 1965. · Zbl 0139.17203 [29] H. Whitney. Congruent Graphs and the Connectivity of Graphs. American Journal of Mathematics.54, 150-168. 1932. · JFM 58.0609.01 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.