.svg){kind=logo}
ALGORITHM FOR FINDING CONNECTED RESOLVING NUMBER OF A GRAPH
Keywords:
domination number, metric dimension, resolving dominating setDOI:
https://doi.org/10.17654/0974165825005Abstract
For an ordered subset $\beta=\left\{\beta_1, \beta_2, \ldots, \beta_k\right\}$ of vertices and $v$ in a connected graph $G=(V, E)$, the $k$-vector
$$
r(v \mid \beta)=\left(d\left(v, \beta_1\right), d\left(v, \beta_2\right), d\left(v, \beta_k\right)\right)
$$
is the metric representation of vertex $v$ with respect to $\beta$. $\beta$ is a resolving set for $G$ if various vertices of $G$ have different representations with respect to $\beta$. A minimum resolving set is the lowest cardinality resolving set and $\operatorname{dim}(G)$ is the cardinality of the dimension of $G$. A resolving set $B$ of $G$ is connected if the subgraph $\bar{B}$ 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 $\operatorname{cdim}(G)$, 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.
Received: August 3, 2024
Revised: September 23, 2024
Accepted: October 26, 2024
References
F. Harary and R. A. Melter, On the metric dimension of a graph, Ars Combin. 2(191-195) (1976), 1.
P. J. Slater, Leaves of trees, Congr. Numer. 14(549-559) (1975), 37.
R. A. Melter and I. Tomescu, Metric bases in digital geometry, Computer Vision, Graphics, and Image Processing 25(1) (1984), 113-121.
S. Khuller, B. Raghavachari and A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70(3) (1996), 217-229.
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.
I. Tomescu, I. Javaid and I. Slamin, On the partition dimension and connected partition dimension of wheels, Ars Combin. 84 (2007), 311-318.
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.
I. Javaid, M. T. Rahim and K. Ali, Families of regular graphs with constant metric dimension, Util. Math. 75(1) (2008), 21-33.
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.
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.
F. Muhammad and L. Susilowati, Algorithm and computer program to determine metric dimension of graph, J. Physics: Conference Series 1494(1) (2020), 1-5.
V. Saenpholphat and P. Zhang, Connected resolvability of graphs, Czechoslovak Math. J. 53 (2003), 827-840.
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.
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.
B. Mohamed and M. Amin, Domination number and secure resolving sets in cyclic networks, Appl. Comput. Math. 12(2) (2023), 42-45.
B. Mohamed, Metric dimension of graphs and its application to robotic navigation, International Journal of Computer Applications 184(15) (2022), 1-3.
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.
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.
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.
B. Mohamed, L. Mohaisen and M. Amin, Binary equilibrium optimization algorithm for computing connected domination metric dimension problem, Scientific Programming 2022 (2022), 1-15.
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.
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.
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.
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.
Downloads
Published
Issue
Section
License
Copyright (c) 2024 PUSHPA PUBLISHING HOUSE, PRAYAGRAJ, INDIA
This work is licensed under a Creative Commons Attribution 4.0 International License.
_________________________
Attribution: Credit Pushpa Publishing House as the original publisher, including title and author(s) if applicable.
Contact Pushpa Publishing House for more info or permissions.
Journal Impact Factor: 
