On Cycle Related Graphs with Constant Metric Dimension

ABSTRACT

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 = {w_{1}, w_{2}, ..., w_{k}} 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,w_{1}), d(v,w_{2}), …, d(v,w_{k})). . 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 T_{n,m} and the graph obtained from prism denoted by 2C_{k} + {x_{k}y_{k}} have constant metric dimension.

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 = {w

Cite this paper

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.

M. Ali, G. Ali, U. Ali and M. Rahim, "On Cycle Related Graphs with Constant Metric Dimension,"

References

[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.

[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.