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), 2023. Published by Science Publishing Group |
Metric Basis, Metric Dimension, Alternate Snake Graphs
| [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 Zn× Zn× Zn 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) ʘ K1 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 fn×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. |
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
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
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
Share This Article
Twitter
Linked In
Facebook
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}
}
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 -
Information
Email: