This paper investigates the NP-hard problem of finding the lowest secure connected domination metric dimension of graphs. If each vertex in G can be uniquely recognized by its vector of distances to   the vertices in Scddim, then every vertex set Scddim of a connected graph  resolves G. If the subgraph induced by Scddim is a nontrivial connected subgraph of G, then the resolving set Scddim of G is connected. That resolving set is dominating if each vertex in G that is not an element of Scddim is a neighbor of some vertices in Scddim. If there is a v in D such that  is a dominating set for any u in  then the dominating set D is secure. If for every  there exists  such that  is a resolving set, then the resolving set R is secure. These four cardinality values are the metric dimension of G, the connected metric dimension of G, the secure metric dimension of G, and the connected domination metric dimension of G, respectively. They correspond to the cardinality of the smallest resolving set of G, the minimal connected resolving set, the minimal secure resolving set, and the minimal connected domination resolving set. In this paper, we introduce the secure connected dominant metric dimension of some graphs such as triangular snake graph, path graph, star tree and alternate quadrilateral snake. In particular, we derive the explicit formulas for the subdivision of triangular snake graph, alternate triangular snake graph, total graph of  cycle graph and bistar tree.

resolving set, connected domination resolving set, domination resolving set, secure resolving set.

Received: September 2, 2024; Accepted: December 10, 2024; Published: January 6, 2025

How to cite this article: Yasser M. Hausawi, Zaid Alzaid, Olayan Alharbi, Badr Almutairi and Basma Mohamed, Computing the secure connected dominant metric dimension problem of classes of graphs, Advances and Applications in Discrete Mathematics 42(3) (2025), 219-233. https://doi.org/10.17654/0974165825015

This Open Access Article is Licensed under Creative Commons Attribution 4.0 International License

References:
[1] N. Vesselinova, R. Steinert, D. F. Perez-Ramirez and M. Boman, Learning combinatorial optimization on graphs: A survey with applications to networking, IEEE Access 8 (2020), 120388-120416.
[2] A. Sebő and E. Tannier, On metric generators of graphs, Mathematics of Operations Research 29(2) (2004), 383-393.
[3] C. Glazik, G. Jäger, J. Schiemann and A. Srivastav, Bounds for the static permutation mastermind game, Discrete Mathematics 344(3) (2021), 112253.
[4] A. Berger, C. Chute and M. Stone, Query complexity of mastermind variants, Discrete Mathematics 341(3) (2018), 665-671.
[5] Y. Chen, M. Rohrbach, Z. Yan, Y. Shuicheng, J. Feng and Y. Kalantidis, Graph-based global reasoning networks, In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2019, pp. 433-442.
[6] Z. Li, Q. Chen and V. Koltun, Combinatorial optimization with graph convolutional networks and guided tree search, Advances in Neural Information Processing Systems (2018), 31.
[7] M. Gasse, D. Chételat, N. Ferroni, L. Charlin and A. Lodi, Exact combinatorial optimization with graph convolutional neural networks, Advances in Neural Information Processing Systems (2019), 32.
[8] A. Ortega, P. Frossard, J. Kovačević, J. M. Moura and P. Vandergheynst, Graph signal processing: Overview, challenges, and applications, Proceedings of the IEEE 106(5) (2018), 808-828.
[9] M. K. Sohrabi and H. Azgomi, A survey on the combined use of optimization methods and game theory, Archives of Computational Methods in Engineering 27(1) (2020), 59-80.
[10] G. Chartrand, L. Eroh, M. A. Johnson and O. R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Applied Mathematics 105(1-3) (2000), 99-113.
[11] P. J. Slater, Leaves of trees, In Proceedings of the 6th Southeast Conference on Combinatorics, Graph Theory and Computing, Boca Raton, FL, USA, 17-20 February 1975, pp. 549-559.
[12] P. J. Slater, Dominating and reference sets in a graph, J. Math. Phys. Sci. 22(4) (1988), 445-455.
[13] F. Harary and R. A. Melter, On the dimension of unicyclic graphs, J. Combinat. Math. Combinat. Comput. 40(4) (2002), 17-32.
[14] M. M. AlHoli, O. A. AbuGhneim and H. A. Ezeh, Metric dimension of some path related graphs, Global Journal of Pure and Applied Mathematics 3(2) (2017), 149 157.
[15] A. T. Shahida and M. S. Sunitha, On the metric dimension of joins of two graphs, Int. J. Sci. Eng. Res. 5 (2014), 33-38.
[16] M. Ali, M. T. Rahim and G. Ali, On two families of graphs with constant metric dimension, Journal of Prime Research in Mathematics 8 (2012), 95-101.
[17] V. Saenpholphat and P. Zhang, Connected resolvability of graphs, Czechoslovak Mathematical Journal 53 (2003), 827-840.
[18] L. Eroh, C. X. Kang and E. Yi, The connected metric dimension at a vertex of a graph, Theoretical Computer Science 806 (2020), 53-69.
[19] A. M. Naji and N. D. Soner, Resolving connected domination in graphs, Mathematical Combinatorics 4 (2015), 129-136.
[20] H. Subramanian and S. Arasappan, Secure resolving sets in a graph, Symmetry 10(10) (2018), 439.
[21] B. Mohamed and M. Amin, Domination number and secure resolving sets in cyclic networks, Applied and Computational Mathematics 12(2) (2023), 42-45.
[22] B. Mohamed, L. Mohaisen and M. Amin, Computing connected resolvability of graphs using binary enhanced Harris Hawks optimization, Intelligent Automation and Soft Computing 36(2) (2023), 2349-2361.
[23] B. Mohamed, L. Mohaisen and M. Amin, Binary equilibrium optimization algorithm for computing connected domination metric dimension problem, Scientific Programming 2022 (2022), 1-15.
[24] B. Mohamed and M. Amin, The metric dimension of subdivisions of Lilly graph, Tadpole Graph and Special Trees, Applied and Computational Mathematics 12(1) (2023), 9-14.
[25] X. Zuo, A. Ali, G. Ali, M. K. Siddiqui, M. T. Rahim and A. Asare-Tuah, On constant metric dimension of some generalized convex polytopes, Journal of Mathematics 2021 (2021), 1-7.
[26] B. Mohamed, Metric dimension of graphs and its application to robotic navigation, International Journal of Computer Applications 184(15) (2022), 1-3.
[27] 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) 15(1) (2023), 1 10.
[28] B. Mohamed, A comprehensive survey on the metric dimension problem of graphs and its types, International Journal of Theoretical and Applied Mathematics 9(1) (2023), 1-5.
[29] B. Mohamed, L. Mohaisen and M. Amin, Binary Archimedes optimization algorithm for computing dominant metric dimension problem, Intelligent Automation and Soft Computing 38(1) (2023), 1-16.
[30] I. M. Batiha, N. Anakira, A. Hashim and B. Mohamed, A special graph for the connected metric dimension of graphs, Mathematical Models in Engineering (2024), 1-9.
[31] M. I. Batiha, M. Amin, B. Mohamed and H. I. Jebril, Connected metric dimension of the class of ladder graphs, Mathematical Models in Engineering 10(2) (2024), 65-74. https://doi.org/10.21595/mme.2024.23934
[32] P. Agasthi and N. Parvathi, On some labelings of triangular snake and central graph of triangular snake graph, In Journal of Physics: Conference Series 1000(1) 2018, p. 012170. IOP Publishing.
[33] S. K. Vaidya and N. B. Vyas, Product cordial labeling for alternate snake graphs, Malaya Journal of Matematik 2(03) (2014), 188-196.
[34] N. Inayah, I. W. Sudarsana, S. Musdalifah and N. Daeng Mangesa, On super mean labeling for total graph of path and cycle, International Journal of Mathematics and Mathematical Sciences (2018), 1-5.
[35] K. B. Smitha and K. Thirusangu, Distance two labeling of quadrilateral snake families, International Journal of Pure and Applied Mathematical Sciences 9(2) (2016), 283-298.
[36] G. Ramesh and A. Rajasekaran, Some applications of pair resolving sets, International Journal for Research in Engineering Application and Management 4(7) (2018), 117-121.