You are here

Home » Content

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

Journal Name:

  • European Journal of Pure and Applied Mathematics

Publication Year:

  • 2012

Key Words:

Author NameUniversity of Author

AMS Codes:

Abstract (2. Language): 
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 cardinality of a set of vertices such that every vertex of G is uniquely determined by its vector of 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 ⌈log2(G)⌉ ≤ dim(G⋆) ≤ n − 1, for a simple and connected graph G of order n ≥ 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⋆)} equals dim(G), dim(L(G)), and dim(G⋆), respectively. We conclude this paper with some open problems.
Bookmark/Search this post with
FULL TEXT (PDF): 
PDF icon arastirmax-comparison-metric-dimension-graphs-line-graphs-and-line-graphs-subdivision-graphs.pdf
  • 3
302-316
  • English

REFERENCES

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.
[2] L.W. Beineke. Characterizations of Derived Graphs. Journal of Combinatorial Theory. 9,
129-135. 1970.
[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.
[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.
[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.
[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.
[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.
[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.
[10] M. Feng, M. Xu, and K. Wang. On the metric dimension of line graphs.
arXiv:1107.4140v1.
[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.
[13] F. Harary and R.A. Melter. On the metric dimension of a graph. Ars Combinatoria. 2,
191-195. 1976.
[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.
[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.
[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.
[17] S. Khuller, B. Raghavachari, and A. Rosenfeld. Landmarks in Graphs. Discrete Applied
Mathematics. 70, 217-229. 1996.
[18] J. Krausz. Demonstration nouvelle d’une Théorème de Whitney sur les Réseaux. Mat.
Fiz. Lapok 50, 75-85. 1943.
[19] C. Poisson and P. Zhang. The Metric Dimension of Unicyclic Graphs. Journal of Combinatorial
Mathematics and Combinatorial Computing. 40, 17-32. 2002.
[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.
[22] C. Sandorfy. LCAO MO Calculations on Saturated Hydrocarbons and Their Substituted
Derivatives. Canadian Journal of Chemistry. 33, 1337-1351. 1955.
[23] A. Sebö and E. Tannier. On metric generators of graphs. Mathematics of Operations Research.
29, 383-393. 2004.
[24] B. Shanmukha, B. Sooryanarayana, and K.S. Harinath. Metric dimension of wheels. Far
East Journal of Applied Mathematics. 8 (3), 217-229. 2002.
[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 Physical
Sciences. 22, 445-455. 1998.
[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.
[29] H. Whitney. Congruent Graphs and the Connectivity of Graphs. American Journal of
Mathematics. 54, 150-168. 1932.

Thank you for copying data from http://www.arastirmax.com