On Cycle Related Graphs with Constant Metric Dimension
Murtaza Ali, Gohar Ali, Usman Ali, M. T. Rahim
DOI: 10.4236/ojdm.2012.21005   PDF    HTML   XML   5,917 Downloads   12,836 Views   Citations


If G is a connected graph, the distance d (u,v) between two vertices u,v ∈ V(G) is the length of a shortest path between them. Let W = {w1, w2, ..., wk} be an ordered set of vertices of G and let v be a vertex of G . The repre-sentation r(v|W) of v with respect to W is the k-tuple (d(v,w1), d(v,w2), …, d(v,wk)). . If distinct vertices of G have distinct representations with respect to W , then W is called a resolving set or locating set for G. A re-solving set of minimum cardinality is called a basis for G and this cardinality is the metric dimension of G , denoted by dim (G). A family ? of connected graphs is a family with constant metric dimension if dim (G) is finite and does not depend upon the choice of G in ?. In this paper, we show that dragon graph denoted by Tn,m and the graph obtained from prism denoted by 2Ck + {xkyk} have constant metric dimension.

Share and Cite:

M. Ali, G. Ali, U. Ali and M. Rahim, "On Cycle Related Graphs with Constant Metric Dimension," Open Journal of Discrete Mathematics, Vol. 2 No. 1, 2012, pp. 21-23. doi: 10.4236/ojdm.2012.21005.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] J. Caceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara and D. R. Wood, “On the Metric Dimension of Some Families of Graphs,” Electronic Notes in Discrete Mathematics, Vol. 22, 2005, pp. 129- 133.
[2] G. Chartrand, L. Eroh, M. A. Johnson and O. R. Oellermann, “Resolvability in Graphs and Metric Dimension of a Graph,” Discrete Applied Mathematics, Vol. 105, 2000, pp. 99-113. doi:10.1016/S0166-218X(00)00198-0
[3] F. Harary and R. A. Melter, “On the Metric Dimension of a Graph,” Ars Combinatoria, Vol. 2, 1976, pp. 191-195.
[4] I. Javaid, M. T. Rahim and K. Ali, “Families of Regular Graphs with Constant Metric Dimension,” Utilitas Ma- thematica, Vol. 75, 2008, pp. 21-33.
[5] S. Khuller, B. Raghavachari and A. Rosenfeld, “Locali- zation in Graphs,” Technical Report CS-TR-3326, Uni- versity of Maryland at College Park, 1994.
[6] R. A. Melter and I. Tomescu, “Metric Bases in Digital Geometry,” Computer Vision, Graphics, and Image Pro- cessing, Vol. 25, No. 1, 1984, pp. 113-121. doi:10.1016/0734-189X(84)90051-3
[7] P. J. Slater, “Dominating and Reference Sets in Graphs,” Journal of Mathematical Physics, Vol. 22, 1998, pp. 445-455.
[8] I. Tomescu and I. Javaid, “On the Metric Dimension of the Jahangir Graph,” Bulletin Mathématique de la Société des Sciences. Mathématiques de Roumanie, Vol. 50, No. 4, 2007, pp. 371-376.
[9] K. Karliraj and V. J. Vernold, “On Equatable Coloring of Helm and Gear Graphs,” International Journal of Mathe- matical Combinatorics, Vol. 4, No. 1, 2010, pp. 32-37.
[10] I. Javaid, “On the Connected Partition Dimension of Unicyclic Graphs,” Journal of Combinatorial Mathe- matics and Combinatorial, Vol. 65, 2008, pp. 71-77.
[11] I. Javaid and S. Shokat, “On the Patition Dimension of Some Wheel Related Graph,” Journal of Prime Research in Mathematics,Vol. 4, 2008, pp. 154-164.
[12] M. Ali, M. Imran, A. Q. Baig, M. K. Shafiq and G. Ali, “On the Metric Dimension of Mobius Ladders,” Ars Combinatoria, in press.
[13] I. Tomescu, I. Javaid, et al., “On the Patition Dimension and Connected Partition Dimension Wheels,” Ars Com- binatoria, Vol. 84, 2007, pp. 311-317.
[14] I. Javaid, et al., “Fault-Tolerance in Resolvibility,” Utilitas Mathematica, Vol. 80, 2009, pp. 263-275.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.