Mathematics and Computer Science

Research Article | | Peer-Reviewed |

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

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

Share This Article

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.

DOI 10.11648/j.mcs.20230804.12
Published in Mathematics and Computer Science (Volume 8, Issue 4, July 2023)
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 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.
Cite This Article
  • 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
  • Department of Computer Science, Faculty of Computers and Artificial Intelligence, AlRyada University for Science and Technology, Sadat City, Egypt

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

  • Sections