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,436
Downloads
11,473
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 = {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.

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

Journals Menu

Copyright © 2020 by authors and Scientific Research Publishing Inc.

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