Mathematics and Computer Science

Submit a Manuscript

Publishing with us to make your research visible to the widest possible audience.

Propose a Special Issue

Building a community of authors and readers to discuss the latest research and develop new ideas.

Research Article |

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

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.

Metric Basis, Metric Dimension, Alternate Snake Graphs

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

Copyright © 2023 Authors retain the copyright of this article.
This article is an open access article distributed under the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/) which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

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.