On Computing the Metric Dimension of the Families of Alternate Snake Graphs

Basma Mohamed; Mohamed Amin

doi:doi:10.11648/j.mcs.20230804.12

Research Article |

| Peer-Reviewed

On Computing the Metric Dimension of the Families of Alternate Snake Graphs

Basma Mohamed, Mohamed Amin

Published in Mathematics and Computer Science (Volume 8, Issue 4)

Received: 13 September 2023 Accepted: 8 October 2023 Published: 30 October 2023

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

Consider a robot that is trying to determine its current location while navigating a graph-based environment. To know how distant it is from each group of fixed landmarks, it can send a signal. We handle the problem of precisely identifying the minimum number of landmarks needed and their ideal placement to guarantee the robot can always discover itself. The number of landmarks in the graph is its metric dimension, and the collection of nodes on which they are distributed is its metric basis. The smallest group of nodes required to uniquely identify each other node in a graph using shortest path distances is known as the metric dimension of the graph. We consider the NP-hard problem of finding the metric dimension of graphs. A set of vertices B of a connected graph G resolves G if every vertex of G is uniquely identified by its vector of distances to the vertices in B. The minimum resolving set is called the metric basis and the cardinality of the basis is called the metric dimension of G. Metric dimension has applications in a wide range of areas such as robot navigation, telecommunications, combinatorial optimization, and pharmacocatual chemistry. In this paper, we determine the metric dimension of the family of alternate snake graphs including alternate snake, alternate k-polygonal snake, double alternate triangular snake and triple alternate triangular snake graph.

Published in	Mathematics and Computer Science (Volume 8, Issue 4)
DOI	10.11648/j.mcs.20230804.12
Page(s)	94-103
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), 2024. Published by Science Publishing Group

Keywords

Metric Basis, Metric Dimension, Alternate Snake Graphs

References

[1]	Slater, P. J. Leaves of trees. Congr Numer. 1975; 14, 549–559.
[2]	Slater, PJ. Dominating and reference sets in a graph. J. Math Phys Sci. 1998; 22: 445-455.
[3]	Harary, F.; Melter, R. A. On the metric dimension of graph. Ars Comb. 1976, 24, 191–195.
[4]	Khuller, S.; Raghavachari, B.; Rosenfeld, A. Localization in Graphs; Technical Report CS-TR-3326; University of Maryland at College Park: College Park, MD, USA, 1994.
[5]	Manjusha, R.; Sunny Kuriakose, A. Metric dimension and uncertainty of traversing robots in a network. Int J Appl Graph Theory Wirel Ad Hoc Networks Sens Networks. 2015, 7, 1-9.‏
[6]	Chartrand, G.; Eroh, L.; Johnson, M. A.; Oellermann, O. R. Resolvability in graphs and the metric dimension of a graph. Discret Appl Math. 2000, 105, 99–113.
[7]	Melter, R. A.; Tomescu, I. Metric bases in digital geometry, Computer vision. Gr. Image Process. 1984, 25, 113–121.
[8]	Idrees, M.; Ma, H.; Wu, M.; Nizami, A. R.; Munir, M.; Ali, S. Metric Dimension of Generalized Möbius Ladder and its Application to WSN Localization. J. Adv. Comput. Intell. Intell. Inform. 2020, 24, 3-11.‏
[9]	Saputro, S. W., Simanjuntak, R..; Uttunggadewa, S. The metric dimension of the lexicographic product of graphs. Discrete Math. 2013, 313, 1045-1051.
[10]	Nawaz, S.; Ali, M.; Khan, M. A.; Khan, S. Computing Metric Dimension of Power of Total Graph. IEEE Access. 2021, 9, 74550-74561.
[11]	Nazeer S.; Hussain, M.; Alrawajeh F. A.; Almotairi, S. Metric Dimension on Path-Related Graphs. Math. Probl. Eng. 2021.
[12]	Ahmad, A.; Bača, M.; Sultan, S. Computing the metric dimension of Kayak Paddles graph and Cycles with chord. Proyecciones. 2020, 39, 287-300.
[13]	Borchert, A.; Gosselin, S. The metric dimension of circulant graphs and Cayley hypergraphs. Util. Math. 2018, 106, 125-147.
[14]	Imran, M.; Siddiqui, M. K.; Naeem, R. On the metric dimension of generalized petersen multigraphs. IEEE Access. 2018, 6, 74328-74338.‏
[15]	Jäger, G.; Drewes, F. The metric dimension of Z_n× Z_n× Z_n is 3n/2. Theor. Comput. Sci. 2020, 806, 344-362.‏
[16]	Ahmad, Z.; Chaudhary, M. A.; Baig, A. Q.; Zahid, M. A. On metric dimension of P (n,2) ʘ K₁ graph. J. Discrete Math. Sci. Cryptogr. 2021, 24, 629-645.
[17]	Imran, M.; Baig, A. Q.; Shafiq, M. K. Classes of convex polytopes with constant. Util. Math. 2013, 90, 85-99.
[18]	Imran, M.; AHMAD, A.; SEMANIČOVÁ-FEŇOVČÍKOVÁ, A. On classes of regular graphs with constant metric dimension. Acta Math. Sci. 2013, 33, 187-206.
[19]	Imran, M.; Bashir, F.; Baig, A. Q.; Bokhary, A. U. H.; Riasat, A.; Tomescu, I. On metric dimension of flower graphs f_n×m and convex polytopes.‏ Util. Math. 2013, 92, 389–409.
[20]	Zuo, X.; Ali, A.; Ali, G.; Siddiqui, M. K.; Rahim, M. T.; Asare-Tuah, A. On Constant Metric Dimension of Some Generalized Convex Polytopes. J. Math. 2021.‏
[21]	Imran, S., Siddiqui, M. K., Imran, M., Hussain, M., Bilal, H. M., Cheema, I. Z.,. & Saleem, Z. Computing the metric dimension of gear graphs. Symmetry, 2018, 10 (6), 209.
[22]	Pan, H., Ali, M., Ali, G., Rahim, M. T., & Yang, X. On the families of graphs with unbounded metric dimension, IEEE Access, 2019.
[23]	Siddiqui, H. M. A. & Imran, M. Computing the metric dimension of wheel related graphs. Applied mathematics and computation, 2014, 242, 624-632.
[24]	B. Mohamed, L. Mohaisen and M. Amin,"Binary Equilibrium Optimization Algorithm for Computing Connected Domination Metric Dimension Problem," Scientific Programming, vol. 2022, 2022.
[25]	B. Mohamed, L. Mohaisen and M. Amin," Computing Connected Resolvability of Graphs Using Binary Enhanced Harris Hawks Optimization," Intelligent Automation & Soft Computing, vol. 36, no. 2, 2023.
[26]	B. Mohamed and M. Amin, "The Metric Dimension of Subdivisions of Lilly Graph, Tadpole Graph and Special Trees," Applied and Computational Mathematics, vol. 12, no. 1, pp. 9-14, 2023.
[27]	B. Mohamed and M. Amin, "Domination Number and Secure Resolving Sets in Cyclic Networks," Applied and Computational Mathematics, vol. 12, no. 2, pp. 42-45, 2023.
[28]	B. Mohamed, Metric Dimension of Graphs and its Application to Robotic Navigation, International Journal of Computer Applications, vol. 184, no. 15, 2022.
[29]	I. H. Jebril and N. M. Abdelqader,"Hyers-Ulam Stability of Quantum Logic Fuzzy Implication", WSEAS Transactions on Information Science and Applications, vol. 20, pp. 131-135, 2023.
[30]	B. Mohamed and M. Amin, "A hybrid optimization algorithms for solving metric dimension problem," International Journal on Applications of Graph Theory in Wireless Ad hoc Networks and Sensor Networks (GRAPH-HOC), vol. 15, no. 1, 2023.
[31]	B. Mohamed, "A Comprehensive Survey on the Metric Dimension Problem of Graphs and Its Types, International Journal of Theoretical and Applied Mathematics, vol. 9, no. 1, 2023.

Cite This Article

Plain Text BibTeX RIS

APA Style

Basma Mohamed, Mohamed Amin. (2023). On Computing the Metric Dimension of the Families of Alternate Snake Graphs. Mathematics and Computer Science, 8(4), 94-103. https://doi.org/10.11648/j.mcs.20230804.12

Copy | Download

ACS Style

Basma Mohamed; Mohamed Amin. On Computing the Metric Dimension of the Families of Alternate Snake Graphs. Math. Comput. Sci. 2023, 8(4), 94-103. doi: 10.11648/j.mcs.20230804.12

Copy | Download

AMA Style

Basma Mohamed, Mohamed Amin. On Computing the Metric Dimension of the Families of Alternate Snake Graphs. Math Comput Sci. 2023;8(4):94-103. doi: 10.11648/j.mcs.20230804.12

Copy | Download

@article{10.11648/j.mcs.20230804.12,
  author = {Basma Mohamed and Mohamed Amin},
  title = {On Computing the Metric Dimension of the Families of Alternate Snake Graphs},
  journal = {Mathematics and Computer Science},
  volume = {8},
  number = {4},
  pages = {94-103},
  doi = {10.11648/j.mcs.20230804.12},
  url = {https://doi.org/10.11648/j.mcs.20230804.12},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.mcs.20230804.12},
  abstract = {Consider a robot that is trying to determine its current location while navigating a graph-based environment. To know how distant it is from each group of fixed landmarks, it can send a signal. We handle the problem of precisely identifying the minimum number of landmarks needed and their ideal placement to guarantee the robot can always discover itself. The number of landmarks in the graph is its metric dimension, and the collection of nodes on which they are distributed is its metric basis. The smallest group of nodes required to uniquely identify each other node in a graph using shortest path distances is known as the metric dimension of the graph. We consider the NP-hard problem of finding the metric dimension of graphs. A set of vertices B of a connected graph G resolves G if every vertex of G is uniquely identified by its vector of distances to the vertices in B. The minimum resolving set is called the metric basis and the cardinality of the basis is called the metric dimension of G. Metric dimension has applications in a wide range of areas such as robot navigation, telecommunications, combinatorial optimization, and pharmacocatual chemistry. In this paper, we determine the metric dimension of the family of alternate snake graphs including alternate snake, alternate k-polygonal snake, double alternate triangular snake and triple alternate triangular snake graph.
},
 year = {2023}
}

Copy | Download

TY - JOUR
T1 - On Computing the Metric Dimension of the Families of Alternate Snake Graphs
AU - Basma Mohamed
AU - Mohamed Amin
Y1 - 2023/10/30
PY - 2023
N1 - https://doi.org/10.11648/j.mcs.20230804.12
DO - 10.11648/j.mcs.20230804.12
T2 - Mathematics and Computer Science
JF - Mathematics and Computer Science
JO - Mathematics and Computer Science
SP - 94
EP - 103
PB - Science Publishing Group
SN - 2575-6028
UR - https://doi.org/10.11648/j.mcs.20230804.12
AB - Consider a robot that is trying to determine its current location while navigating a graph-based environment. To know how distant it is from each group of fixed landmarks, it can send a signal. We handle the problem of precisely identifying the minimum number of landmarks needed and their ideal placement to guarantee the robot can always discover itself. The number of landmarks in the graph is its metric dimension, and the collection of nodes on which they are distributed is its metric basis. The smallest group of nodes required to uniquely identify each other node in a graph using shortest path distances is known as the metric dimension of the graph. We consider the NP-hard problem of finding the metric dimension of graphs. A set of vertices B of a connected graph G resolves G if every vertex of G is uniquely identified by its vector of distances to the vertices in B. The minimum resolving set is called the metric basis and the cardinality of the basis is called the metric dimension of G. Metric dimension has applications in a wide range of areas such as robot navigation, telecommunications, combinatorial optimization, and pharmacocatual chemistry. In this paper, we determine the metric dimension of the family of alternate snake graphs including alternate snake, alternate k-polygonal snake, double alternate triangular snake and triple alternate triangular snake graph.

VL - 8
IS - 4
ER -

Copy | Download

Author Information

Basma Mohamed

Department of Computer Science, Faculty of Computers and Artificial Intelligence, AlRyada University for Science and Technology, Sadat City, Egypt
Mohamed Amin

Mathematics and Computer Science Department, Faculty of Science, Menoufia University, Shebin Elkom, Egypt

Download PDF

Sections

Plain Text BibTeX RIS

APA Style

Basma Mohamed, Mohamed Amin. (2023). On Computing the Metric Dimension of the Families of Alternate Snake Graphs. Mathematics and Computer Science, 8(4), 94-103. https://doi.org/10.11648/j.mcs.20230804.12

Copy | Download

ACS Style

Basma Mohamed; Mohamed Amin. On Computing the Metric Dimension of the Families of Alternate Snake Graphs. Math. Comput. Sci. 2023, 8(4), 94-103. doi: 10.11648/j.mcs.20230804.12

Copy | Download

AMA Style

Basma Mohamed, Mohamed Amin. On Computing the Metric Dimension of the Families of Alternate Snake Graphs. Math Comput Sci. 2023;8(4):94-103. doi: 10.11648/j.mcs.20230804.12

Copy | Download

@article{10.11648/j.mcs.20230804.12,
  author = {Basma Mohamed and Mohamed Amin},
  title = {On Computing the Metric Dimension of the Families of Alternate Snake Graphs},
  journal = {Mathematics and Computer Science},
  volume = {8},
  number = {4},
  pages = {94-103},
  doi = {10.11648/j.mcs.20230804.12},
  url = {https://doi.org/10.11648/j.mcs.20230804.12},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.mcs.20230804.12},
  abstract = {Consider a robot that is trying to determine its current location while navigating a graph-based environment. To know how distant it is from each group of fixed landmarks, it can send a signal. We handle the problem of precisely identifying the minimum number of landmarks needed and their ideal placement to guarantee the robot can always discover itself. The number of landmarks in the graph is its metric dimension, and the collection of nodes on which they are distributed is its metric basis. The smallest group of nodes required to uniquely identify each other node in a graph using shortest path distances is known as the metric dimension of the graph. We consider the NP-hard problem of finding the metric dimension of graphs. A set of vertices B of a connected graph G resolves G if every vertex of G is uniquely identified by its vector of distances to the vertices in B. The minimum resolving set is called the metric basis and the cardinality of the basis is called the metric dimension of G. Metric dimension has applications in a wide range of areas such as robot navigation, telecommunications, combinatorial optimization, and pharmacocatual chemistry. In this paper, we determine the metric dimension of the family of alternate snake graphs including alternate snake, alternate k-polygonal snake, double alternate triangular snake and triple alternate triangular snake graph.
},
 year = {2023}
}

Copy | Download

VL - 8
IS - 4
ER -

Copy | Download