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

Basma Mohamed; Mohamed Amin

doi:doi:10.11648/j.acm.20231201.12

| Peer-Reviewed

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

Basma Mohamed, Mohamed Amin

Published in Applied and Computational Mathematics (Volume 12, Issue 1)

Received: 28 October 2022 Accepted: 16 November 2022 Published: 16 March 2023

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

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 F_n, Lollipop Graph L_m,n and Petersen Graph P_n,_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 Z_n× Z_n× Z_n 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

Plain Text BibTeX RIS

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

Basma Mohamed

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

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

Download PDF

Sections

Plain Text BibTeX RIS

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