For an ordered subset  of vertices and v in a connected graph  the k-vector is the metric representation of vertex v with respect to is a resolving set for G if various vertices of G have different representations with respect to  A minimum resolving set is the lowest cardinality resolving set and  is the cardinality of the dimension of G. A resolving set B of G is connected if the subgraph  produced by B is a nontrivial connected subgraph of G. The cardinality of the minimal resolving set is the metric dimension of G, while the cardinality of the lowest connected resolving set is the connected metric dimension of G. A connected metric dimension of G, denoted by  is the lowest cardinality of a connected resolving set. The connected resolving number of a graph can be found using the algorithm presented in this work.

domination number, metric dimension, resolving dominating set.

Received: August 3, 2024; Revised: September 23, 2024; Accepted: October 26, 2024; Published: November 23, 2024

How to cite this article: Yasser M. Hausawi, Mohammed El-Meligy, Zaid Alzaid, Olayan Alharbi, Badr Almutairi and Basma Mohamed, Algorithm for finding connected resolving number of a graph, Advances and Applications in Discrete Mathematics 42(1) (2025), 69-77. https://doi.org/10.17654/0974165825005

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

References
[1] F. Harary and R. A. Melter, On the metric dimension of a graph, Ars Combin. 2(191-195) (1976), 1.
[2] P. J. Slater, Leaves of trees, Congr. Numer. 14(549-559) (1975), 37.
[3] R. A. Melter and I. Tomescu, Metric bases in digital geometry, Computer Vision, Graphics, and Image Processing 25(1) (1984), 113-121.
[4] S. Khuller, B. Raghavachari and A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70(3) (1996), 217-229.
[5] 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.
[6] I. Tomescu, I. Javaid and I. Slamin, On the partition dimension and connected partition dimension of wheels, Ars Combin. 84 (2007), 311-318.
[7] G. Chartrand, L. Eroh, M. A. Johnson and O. R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105(1-3) (2000), 99-113.
[8] I. Javaid, M. T. Rahim and K. Ali, Families of regular graphs with constant metric dimension, Util. Math. 75(1) (2008), 21-33.
[9] Z. Ahmad, M. A. Chaudhary, A. Q. Baig and M. A. Zahid, On metric dimension of graph, J. Discrete Math. Sci. Cryptogr. 24(2) (2021), 629-645.
[10] S. Kurniawati, D. A. R. Wardani and E. R. Albirri, On resolving domination number of friendship graph and its operation, J. Physics: Conference Series 1465(1) (2020), 1-9.
[11] F. Muhammad and L. Susilowati, Algorithm and computer program to determine metric dimension of graph, J. Physics: Conference Series 1494(1) (2020), 1-5.
[12] V. Saenpholphat and P. Zhang, Connected resolvability of graphs, Czechoslovak Math. J. 53 (2003), 827-840.
[13] L. Eroh, C. X. Kang and E. Yi, The connected metric dimension at a vertex of a graph, Theoret. Comput. Sci. 806 (2020), 53-69.
[14] B. Mohamed, A comprehensive survey on the metric dimension problem of graphs and its types, International Journal of Theoretical and Applied Mechanics 9(1) (2023), 1-5.
[15] B. Mohamed and M. Amin, Domination number and secure resolving sets in cyclic networks, Appl. Comput. Math. 12(2) (2023), 42-45.
[16] B. Mohamed, Metric dimension of graphs and its application to robotic navigation, International Journal of Computer Applications 184(15) (2022), 1-3.
[17] 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.
[18] B. Mohamed, L. Mohaisen and M. Amin, Computing connected resolvability of graphs using binary enhanced Harris Hawks optimization, Intelligent Automation & Soft Computing 36(2) (2023), 2349-2361.
[19] B. Mohamed and M. Amin, The metric dimension of subdivisions of Lilly graph, tadpole graph and special trees, Appl. Comput. Math. 12(1) (2023), 9-14.
[20] B. Mohamed, L. Mohaisen and M. Amin, Binary equilibrium optimization algorithm for computing connected domination metric dimension problem, Scientific Programming 2022 (2022), 1-15.
[21] A. Asiri and B. Mohamed, Binary fruit fly optimization algorithm for counting the number of spanning trees in networks, Advances and Applications in Discrete Mathematics 41(8) (2024), 663-676.
[22] S. Almotairi, O. Alharbi, Z. Alzaid, Y. Hausawi, J. Almutairi and B. Mohamed, Secure dominant metric dimension of new classes of graphs, Kongzhi yu Juece/Control and Decision 39(5) (2024), 2705-2714.
[23] H. Iswadi, E. T. Baskoro, A. N. M. Salman and R. Simanjuntak, The resolving graph of amalgamation of cycles, Util. Math. 83 (2010), 121-132.
[24] M. I. Batiha, N. Anakira, A. Hashim and B. Mohamed, A special graph for the connected metric dimension of graphs, Mathematical Models in Engineering 10(3) (2024), 193-201. https://doi.org/10.21595/mme.2024.24176.