OJDM  Vol.2 No.1 , January 2012
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 = {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.

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

 
 
Top