| Peer-Reviewed

The Metric Dimension of Subdivisions of Lilly Graph, Tadpole Graph and Special Trees

Received: 28 October 2022     Accepted: 16 November 2022     Published: 16 March 2023
Views:       Downloads:
Abstract

Consider a robot that is navigating in a space represented by a graph and wants to know its current location. It can send a signal to find out how far it is from each set of fixed landmarks. We study the problem of computing the minimum number of landmarks required, and where they should be placed so that the robot can always determine its location. The set of nodes where the landmarks are located is called the metric basis of the graph, and the number of landmarks is called the metric dimension of the graph. On the other hand, the metric dimension of a graph G is the smallest size of a set B of vertices that can distinguish each vertex pair of G by the shortest-path distance to some vertex in B. The finding of the metric dimension of an arbitrary graph is an NP-complete problem. Also, the metric dimension has several applications in different areas, such as geographical routing protocols, network discovery and verification, pattern recognition, image processing, and combinatorial optimization. In this paper, we study the metric dimension of subdivisions of several graphs, including the Lilly graph, the Tadpole graph, and the special trees star tree, bistar tree, and coconut tree.

Published in Applied and Computational Mathematics (Volume 12, Issue 1)
DOI 10.11648/j.acm.20231201.12
Page(s) 9-14
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2023. Published by Science Publishing Group

Keywords

Resolving Set, Metric Dimension, Tadpole Graph, Bistar Tree, Coconut Tree

References
[1] P. J. Slater, “Leaves of Trees,” Congressus Numerantium, Vol. 14, pp. 549-559, 1975.
[2] P. J. Slater, “Dominating and Reference Sets in Graphs,” Journal of Mathematical Physics, Vol. 22, no. 4, pp. 445-455, 1998.
[3] F. Harary and R. A. Melter, “On the Metric Dimension of a Graph,” Ars Combinatoria, Vol. 2, pp. 191-195, 1976.
[4] S. Khuller, B. Raghavachari and A. Rosenfeld, “Localization in Graphs,” Technical Report CS-TR-3326, Universityof Maryland at CollegePark, 1994.
[5] R. Manjusha and AS. Kuriakose, “Metric dimension and uncertainty of traversing robots in a network”, International Journal on Applications of Graph Theory in Wireless Ad hoc Networks and Sensor Networks (GRAPH-HOC), Vol. 7, no. 2/3, pp. 1-9, 2015.‏
[6] G. Chartrand, L. Eroh, M. A. Johnson and O. R. Oellermann, “Resolvability in graphs and the metric dimension of a graph”, Discrete Applied Mathematics, Vol. 105, no. 1-3, pp. 99–113, 2000.
[7] R. A. Melter and I. Tomescu, “Metric Bases in Digital Geometry,” Computer Vision, Graphics, and Image Processing, Vol. 25, no. 1, pp. 113-121, 1984.
[8] M. Idrees, H. Ma, M. Wu, A. R. Nizami, M. Munir and S. Ali, “Metric Dimension of Generalized Möbius Ladder and its Application to WSN Localization”, Journal of Advanced Computational Intelligence and Intelligent Informatics, Vol. 24, pp. 3-11, 2020.
[9] L. Susilowati, S. Zahidah, R. D. Nastiti and M. I. Utoyo, “The metric dimension of k-subdivision graphs”, In Journal of Physics: Conference Series (Vol. 1494, No. 1, p. 012015). IOP Publishing, 2020.
[10] A. Borchert and S. Gosselin,“The metric dimension of circulant graphs and Cayley hypergraphs”, Utilitas Mathematica, vol. 106, pp. 125-147, 2018.
[11] M. Imran, M. K. Siddiqui and R. Naeem, “On the metric dimension of generalized petersen multigraphs”, IEEE Access, Vol. 6, pp. 74328-74338, 2018.‏
[12] S. Nawaz, M. Ali, M. A. Khan and S. Khan, “Computing Metric Dimension of Power of Total Graph”, IEEE Access, vol. 9, pp. 74550-74561, 2021.
[13] S. Nazeer, M. Hussain, F. A. Alrawajeh and S. Almotairi, “Metric Dimension on Path-Related Graphs”, Mathematical Problems in Engineering. 2021.
[14] A. Ahmad, M. Bača and S. Sultan, “Computing the metric dimension of Kayak Paddles graph and Cycles with chord”, Proyecciones, vol. 39, pp. 287-300, 2020.
[15] M. Mulyono and W Wulandari, “The Metric Dimension of Friendship Graph Fn, Lollipop Graph Lm,n and Petersen Graph Pn, m”, Bulletin of Mathematics, Vol. 8, no. 2, pp. 117-124, 2016.
[16] I. J. L. Garces and J. B. Rosario, “Computing the metric dimension of truncated wheels”, 2015.
[17] ‏H. M. A. Siddiqui, and M. Imran, “Computing the metric dimension of wheel related graphs”, Applied mathematics and computation, Vol. 242, pp. 624-632, 2014.
[18] G. Jäger and F. Drewes, “The metric dimension of Zn× Zn× Zn is ⌊3n/2⌋”, Theoretical Computer Science, vol. 806, pp. 344-362, 2020.‏
[19] 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, pp. 371-376, 2007.
[20] I. Tomescu and M. Imran, “R-sets and metric dimension of necklace graphs”, Applied Mathematics and Information Sciences, Vol. 9, no. 1, pp. 63-67, 2015.
[21] M. Imran, A. Q. Baig and M. K. Shafiq,“ Classes of convex polytopes with constant”, Utilitas mathematica, Vol. 90, pp. 85-99, 2013.
[22] M. Imran, A. AHMAD and A. SEMANIČOVÁ-FEŇOVČÍKOVÁ, “On classes of regular graphs with constant metric dimension”, Acta Mathematica Scientia, vol. 33, pp. 187-206, 2013.
[23] M. Imran, F. Bashir, A. Q. Baig, S. A. Bokhary, A. Riasat and I. Tomescu, “On metric dimension of flower graphs fnχm and convex polytopes”, Utilitas mathematica, Vol. 92, pp. 389–409, 2013.
[24] X. Zuo, A. Ali, G. Ali, M. K. Siddiqui, M. T. Rahim and A. Asare-Tuah, “On Constant Metric Dimension of Some Generalized Convex Polytopes”, Journal of Mathematics, vol. 2021, 2021.‏
[25] U. Vaghela and D. Parmar, “Difference perfect square cordial labeling of subdivision of snake graphs”, International Journal of Future Generation Communication and Networking, vol. 13, no. 2, pp. 275-297, 2020.‏
Cite This Article
  • APA Style

    Basma Mohamed, Mohamed Amin. (2023). The Metric Dimension of Subdivisions of Lilly Graph, Tadpole Graph and Special Trees. Applied and Computational Mathematics, 12(1), 9-14. https://doi.org/10.11648/j.acm.20231201.12

    Copy | Download

    ACS Style

    Basma Mohamed; Mohamed Amin. The Metric Dimension of Subdivisions of Lilly Graph, Tadpole Graph and Special Trees. Appl. Comput. Math. 2023, 12(1), 9-14. doi: 10.11648/j.acm.20231201.12

    Copy | Download

    AMA Style

    Basma Mohamed, Mohamed Amin. The Metric Dimension of Subdivisions of Lilly Graph, Tadpole Graph and Special Trees. Appl Comput Math. 2023;12(1):9-14. doi: 10.11648/j.acm.20231201.12

    Copy | Download

  • @article{10.11648/j.acm.20231201.12,
      author = {Basma Mohamed and Mohamed Amin},
      title = {The Metric Dimension of Subdivisions of Lilly Graph, Tadpole Graph and Special Trees},
      journal = {Applied and Computational Mathematics},
      volume = {12},
      number = {1},
      pages = {9-14},
      doi = {10.11648/j.acm.20231201.12},
      url = {https://doi.org/10.11648/j.acm.20231201.12},
      eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.acm.20231201.12},
      abstract = {Consider a robot that is navigating in a space represented by a graph and wants to know its current location. It can send a signal to find out how far it is from each set of fixed landmarks. We study the problem of computing the minimum number of landmarks required, and where they should be placed so that the robot can always determine its location. The set of nodes where the landmarks are located is called the metric basis of the graph, and the number of landmarks is called the metric dimension of the graph. On the other hand, the metric dimension of a graph G is the smallest size of a set B of vertices that can distinguish each vertex pair of G by the shortest-path distance to some vertex in B. The finding of the metric dimension of an arbitrary graph is an NP-complete problem. Also, the metric dimension has several applications in different areas, such as geographical routing protocols, network discovery and verification, pattern recognition, image processing, and combinatorial optimization. In this paper, we study the metric dimension of subdivisions of several graphs, including the Lilly graph, the Tadpole graph, and the special trees star tree, bistar tree, and coconut tree.},
     year = {2023}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - The Metric Dimension of Subdivisions of Lilly Graph, Tadpole Graph and Special Trees
    AU  - Basma Mohamed
    AU  - Mohamed Amin
    Y1  - 2023/03/16
    PY  - 2023
    N1  - https://doi.org/10.11648/j.acm.20231201.12
    DO  - 10.11648/j.acm.20231201.12
    T2  - Applied and Computational Mathematics
    JF  - Applied and Computational Mathematics
    JO  - Applied and Computational Mathematics
    SP  - 9
    EP  - 14
    PB  - Science Publishing Group
    SN  - 2328-5613
    UR  - https://doi.org/10.11648/j.acm.20231201.12
    AB  - Consider a robot that is navigating in a space represented by a graph and wants to know its current location. It can send a signal to find out how far it is from each set of fixed landmarks. We study the problem of computing the minimum number of landmarks required, and where they should be placed so that the robot can always determine its location. The set of nodes where the landmarks are located is called the metric basis of the graph, and the number of landmarks is called the metric dimension of the graph. On the other hand, the metric dimension of a graph G is the smallest size of a set B of vertices that can distinguish each vertex pair of G by the shortest-path distance to some vertex in B. The finding of the metric dimension of an arbitrary graph is an NP-complete problem. Also, the metric dimension has several applications in different areas, such as geographical routing protocols, network discovery and verification, pattern recognition, image processing, and combinatorial optimization. In this paper, we study the metric dimension of subdivisions of several graphs, including the Lilly graph, the Tadpole graph, and the special trees star tree, bistar tree, and coconut tree.
    VL  - 12
    IS  - 1
    ER  - 

    Copy | Download

Author Information
  • Mathematics and Computer Science Department, Faculty of Science, Menoufia University, Shebin El-Kom, Egypt

  • Mathematics and Computer Science Department, Faculty of Science, Menoufia University, Shebin El-Kom, Egypt

  • Sections