Authors:
Basma Mohamed,Iqbal M. Batiha,Nidal Anakira,Mohammad Odeh,Mohammad Shehab,Huda Odetatllah,DOI NO:
https://doi.org/10.26782/jmcms.2025.05.00005Keywords:
Metric Basis,Metric Dimension,Alternate Snake Graph,Abstract
We study the NP-hard problem of determining the secure metric dimension of graphs. A resolving set uniquely identifies each vertex by its distance vector to the set; the smallest is the metric basis, and its size is the metric dimension. A set is secure if each outside vertex can replace an inside one while preserving resolvability. Computing this parameter is NP-complete and has applications in routing, image processing, and network verification. This paper determines the secure metric dimension for alternate snake graphs, including k-polygonal, double, and triple alternate triangular snakesRefference:
I. A. Ahmad, A. N. Koam, M. Azeem, I. Masmali, R. Alharbi. : ‘Edge based metric dimension of various coffee compounds’. PLOS ONE. Vol. 19, No. 4, e0294932, 2024. 10.1371/journal.pone.0294932
II. A. H. Karbasi, R. E. Atani. : ‘Application of dominating sets in wireless sensor networks’. International Journal of Security and Its Applications. Vol. 7, No. 4, pp. 185–202, 2013.
III. B. Mohamed. : ‘A comprehensive survey on the metric dimension problem of graphs and its types’. International Journal of Theoretical and Applied Mechanics. Vol. 9, No. 1, pp. 1–5, 2023. 10.11648/j.ijtam.20230901.11
IV. B. Mohamed, L. Mohaisen, M. Amin. : ‘Binary Archimedes optimization algorithm for computing dominant metric dimension problem’. Intelligent Automation & Soft Computing. Vol. 38, No. 1, pp. 19–34, 2023. 10.32604/iasc.2023.031947
V. B. Mohamed, M. Amin. : ‘Domination number and secure resolving sets in cyclic networks’. Applied and Computational Mathematics. Vol. 12, No. 2, pp. 42–45, 2023. 10.11648/j.acm.20231202.12
VI. B. Mohamed, M. Amin. : ‘Hybridizing slime mould algorithm with simulated annealing for solving metric dimension problem’. Machine Learning Research. Vol. 8, No. 1, pp. 9–16, 2023. 10.11648/j.mlr.20230801.12
VII. C. Zhang, G. Haidar, M. U. I. Khan, F. Yousafzai, K. Hila, A. U. I. Khan. : ‘Constant time calculation of the metric dimension of the join of path graphs’. Symmetry. Vol. 15, No. 3, Article ID 708, 2023. 10.3390/sym15030708
VIII. E. A. Alhenawi, R. A. Khurma, R. Damaševicius, A. G. Hussien. : ‘Solving Traveling Salesman Problem using parallel river formation dynamics optimization algorithm on multi-core architecture using Apache Spark’. International Journal of Computational Intelligence Systems. Vol. 17, No. 1, Article 4, 2024. 10.1007/s44196-023-00385-5
IX. E. Banaian, A. Sen. : ‘A generalization of Markov numbers’. The Ramanujan Journal. Vol. 63, No. 4, pp. 1021–1055, 2024. 10.1007/s11139-023-00801-6
X. E. Hitzer, C. Lavor, D. Hildenbrand. : ‘Current survey of Clifford geometric algebra applications’. Mathematical Methods in the Applied Sciences. Vol. 47, No. 3, pp. 1331–1361, 2024.
XI. F. Harary, R. A. Melter. : ‘On the metric dimension of a graph’. Ars Combinatoria. Vol. 2, pp. 191–195, 1976.
XII. G. Chartrand, L. Eroh, M. A. Johnson, O. R. Oellermann. : ‘Resolvability in graphs and the metric dimension of a graph’. Discrete Applied Mathematics. Vol. 105, Issues 1–3, pp. 99–113, 2000. 10.1016/S0166-218X(00)00198-0
XIII. H. Al-Zoubi, H. Alzaareer, A. Zraiqat, T. Hamadneh, W. Al-Mashaleh. : ‘On ruled surfaces of coordinate finite type’. WSEAS Transactions on Mathematics. Vol. 21, pp. 765–769, 2022. 10.37394/23206.2022.21.87
XIV. H. Subramanian, S. Arasappan. : ‘Secure resolving sets in a graph’. Symmetry. Vol. 10, No. 10, Article 439, 2018. 10.3390/sym10100439
XV. I. M. Batiha, B. Mohamed, I. H. Jebril. : ‘Secure metric dimension of new classes of graphs’. Mathematical Models in Engineering. Vol. 10, No. 3, pp. 1–7, 2024. 10.21595/mme.2024.24168
XVI. I. Peterin, I. G. Yero. : ‘Edge metric dimension of some graph operations’. Bulletin of the Malaysian Mathematical Sciences Society. Vol. 43, No. 3, pp. 2465–2477, 2020. 10.1007/s40840-019-00813-0
XVII. I. Tomescu, M. Imran. : ‘R-sets and metric dimension of necklace graphs’. Applied Mathematics & Information Sciences. Vol. 9, No. 1, pp. 63–67, 2015. 10.18576/amis/090116
XVIII. J. L. Hurink, T. Nieberg. : ‘Approximating minimum independent dominating sets in wireless networks’. Information Processing Letters. Vol. 109, No. 2, pp. 155–160, 2008. 10.1016/j.ipl.2008.09.021
XIX. K. Nie, K. Xu. : ‘The doubly metric dimensions of cactus graphs and block graphs’. Journal of Combinatorial Optimization. Vol. 47, No. 4, pp. 1–17, 2024. 10.1007/s10878-024-01168-0
XX. L. O. Chekhov, M. Shapiro. : ‘Log-canonical coordinates for symplectic groupoid and cluster algebras’. International Mathematics Research Notices. Vol. 2023, No. 11, pp. 9565–9652, 2023. 10.1093/imrn/rnac101
XXI. L. Susilowati, I. Sa’adah, R. Z. Fauziyyah, A. Erfanian. : ‘The dominant metric dimension of graphs’. Heliyon. Vol. 6, No. 3, e03595, 2020. 10.1016/j.heliyon.2020.e03595
XXII. L. Susilowati, R. A. Slamin, A. Rosfiana. : ‘The complement metric dimension of graphs and its operations’. International Journal of Civil Engineering and Technology (IJCIET). Vol. 10, No. 3, pp. 2386–2396, 2019.
XXIII. M. I. Batiha, M. Amin, B. Mohamed, H. I. Jebril. : ‘Connected metric dimension of the class of ladder graphs’. Mathematical Models in Engineering. Vol. 10, No. 2, pp. 65–74, 2024. 10.21595/mme.2024.23391
XXIV. M. Idrees, H. Ma, M. Wu, A. R. Nizami, M. Munir, 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, No. 1, pp. 3–11, 2020. 10.20965/jaciii.2020.p0003
XXV. M. Mulyono, W. Wulandari. : ‘The metric dimension of friendship graph Fn, lollipop graph Lm,n and Petersen graph Pn,m’. Politeia: Jurnal Ilmu Politik. Vol. 8, No. 2, pp. 117–124, 2016.
XXVI. N. Tratnik, D. Ye. : ‘Resonance graphs on perfect matchings of graphs on surfaces’. Graphs and Combinatorics. Vol. 39, No. 4, Article 68, 2023. 10.1007/s00373-023-02666-4
XXVII. P. A. Chusna, I. N. Inayati, M. J. H. Santoso. : ‘The development of math learning media: 3-dimensional snake and ladder’. Al-Adzka: Jurnal Ilmiah Pendidikan Guru Madrasah Ibtidaiyah. Vol. 14, No. 1, pp. 65–78, 2024. 10.18592/aladzkapgmi.v14i1.10842
XXVIII. P. J. Slater. : ‘Dominating and reference sets in a graph’. Journal of Mathematical and Physical Sciences. Vol. 22, No. 4, pp. 445–455, 1988.
XXIX. P. J. Slater. : ‘Leaves of trees’. Congressus Numerantium. Vol. 14, pp. 549–559, 1975.
XXX. P. Shanthi, S. Amutha, N. Anbazhagan, G. Uma, G. P. Joshi, W. Cho. : ‘Characterization of fractional mixed domination number of paths and cycles’. Journal of Mathematics. Vol. 2024, Article ID 6619654, 2024. 10.1155/2024/6619654
XXXI. R. Alfarisi, I. H. Agustin, A. I. Kristiana. : ‘The non-isolated resolving number of k-corona product of graphs’. Journal of Physics: Conference Series. Vol. 1008, No. 1, p. 012040, 2018. 10.1088/1742-6596/1008/1/012040
XXXII. R. A. Melter, I. Tomescu. : ‘Metric bases in digital geometry’. Computer Vision, Graphics, and Image Processing. Vol. 25, No. 1, pp. 113–121, 1984.10.1016/0734-189X(84)90051-3
XXXIII. R. Gao, Y. Xiao, Z. Zhang. : ‘On the metric dimension of circulant graphs’. Canadian Mathematical Bulletin. Vol. 67, No. 2, pp. 328–337, 2024.
XXXIV. R. Hernández-Ortiz, L. P. Montejano, J. A. Rodríguez-Velázquez. : ‘Secure domination in rooted product graphs’. Journal of Combinatorial Optimization. Vol. 41, pp. 401–413, 2021. 10.1007/s10878-020-00558-1
XXXV. R. Manjusha, A. S. 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. 10.5121/jgraphoc.2015.7301
XXXVI. R. Umilasari, L. Susilowati, S. P. Slamin, O. J. Fadekemi. : ‘The local resolving dominating set of comb product graphs’. IAENG International Journal of Computer Science. Vol. 51, No. 2, pp. 115–120, 2024.
XXXVII. S. Almotairi, O. Alharbi, Z. Alzaid, B. Almutairi, B. Mohamed. : ‘The Secure Metric Dimension of the Globe Graph and the Flag Graph’. Advances in Operations Research. Vol. 2024, Article ID 3084976, 2024. 10.1155/2024/3084976
XXXVIII. S. Almotairi, O. Alharbi, Z. Alzaid, Y. M. Hausawi, J. Almutairi, B. Mohamed. : ‘Computing the connected dominant metric dimension of different graphs’. Advances and Applications in Discrete Mathematics. Vol. 41, No. 6, pp. 505–520, 2024.
XXXIX. S. Avadayappan, M. Bhuvaneshwari, P. J. B. Chitra. : ‘Non-isolated resolving number for some splitting graphs’. International Journal of Mathematical Combinatorics. Vol. 1, pp. 9–18, 2018.
XL. S. Gombert, D. Di Mitri, O. Karademir, M. Kubsch, H. Kolbe, S. Tautz, A. Grimm, I. Bohm, K. Neumann, H. Drachsler. : ‘Coding energy knowledge in constructed responses with explainable NLP models’. Journal of Computer Assisted Learning. Vol. 39, No. 3, pp. 767–786, 2023. 10.1111/jcal.12767
XLI. S. Khuller, B. Raghavachari, and A. Rosenfeld. : ‘Localization in graphs’. Technical Report CS-TR-3326, University of Maryland, College Park, 1994.
XLII. S. K. Sharma, V. K. Bhat, P. Singh. : ‘On metric dimension of some planar graphs with 2n odd sided faces’. Discrete Mathematics, Algorithms and Applications. Vol. 16, No. 1, Article ID 2250185, 2024. 10.1142/S1793830922501851
XLIII. S. Lal, V. K. Bhat. : ‘On the dominant local metric dimension of some planar graphs’. Discrete Mathematics, Algorithms and Applications. Vol. 15, No. 7, Article ID 2250152, 2023. 10.1142/S179383092250152X
XLIV. S. Lal, V. K. Bhat. : ‘On the local metric dimension of generalized wheel graph’. Asian-European Journal of Mathematics. Vol. 16, No. 11, Article ID 2350194, 2023. 10.1142/S1793557123501942
XLV. S. M. K. Sarkhi, H. Koyuncu. : ‘Optimization strategies for Atari game environments: Integrating snake optimization algorithm and energy valley optimization in reinforcement learning models’. AI. Vol. 5, No. 3, pp. 1172–1191, 2024. 10.3390/ai5030057
XLVI. S. Nawaz, M. Ali, M. A. Khan, S. Khan. : ‘Computing metric dimension of power of total graph’. IEEE Access. Vol. 9, pp. 74550–74561, 2021. 10.1109/ACCESS.2021.3079734
XLVII. S. W. Saputro, D. Suprijanto, E. T. Baskoro, A. N. M. Salman. : ‘The Metric Dimension of a Graph Composition Products With Star’. Journal of the Indonesian Mathematical Society. Vol. 18, No. 2, pp. 85–92, 2012. 10.22342/jims.18.2.1358.85-92
XLVIII. T. Vetrík, A. Ahmad. : ‘Computing the metric dimension of the categorial product of some graphs’. International Journal of Computer Mathematics. Vol. 94, No. 2, pp. 363–371, 2017. 10.1080/00207160.2015.1123791
XLIX. V. F. Fancy, V. J. A. Cynthia. : ‘Local metric dimension of certain wheel related graphs’. International Journal of Mathematics and Computer Science. Vol. 16, No. 4, pp. 1303–1315, 2021.