Doubly resolving number of the corona product graphs
Abstract
Two vertices u, v in a connected graph G are doubly resolved by vertices x, y of G if d(v, x)−d(u, x)≠d(v, y)−d(u, y). A set W of vertices of the graph G is a doubly resolving set for G if every two distinct vertices of G are doubly resolved by some two vertices of W. Doubly resolving number of a graph G, denoted by ψ(G), is the minimum cardinality of a doubly resolving set for G. In this paper, using adjacency resolving sets and dominating sets of graphs, we study doubly resolving sets in the corona product of graphs G and H, G ⊙ H. First, we obtain the upper and lower bounds for the doubly resolving number of the corona product G ⊙ H in terms of the order of G and the adjacency dimension of H, then we present several conditions that make each of these bounds feasible for the doubly resolving number of G ⊙ H. Also, for some important families of graphs, we obtain the exact value of the doubly resolving number of the corona product.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2025.13.1.15
References
P.S. Buczkowski, G. Chartrand, C. Poisson, and P. Zhang, On k-dimensional graphs and their bases, Period. Math. Hungar. 46 (1) (2003), 9–15.
J. Caceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, and C. Seara, On the metric dimension of some families of graphs, Electron. Notes Discrete Math. 22 (2005), 129–133.
J. Cáceres, C. Hernando, M. Mora, I.M. Pelayo, M.L. Puertas, C. Seara, and D.R. Wood, On the metric dimension of cartesian products of graphs, SIAM J. Discrete Math. 21 (2) (2007), 423–441.
M. Čangalović, J. Kratica, V. Kovačević-Vujčić, and M. Stojanović, Minimal doubly resolving sets of Prism graphs, Optimization 62 (2013), 1037–1043.
H. Fernau and J.A. Rodríguez-Velázquez, On the (adjacency) metric dimension of corona and strong product graphs and their local variants: Combinatorial and computational results, Discrete Appl. Math. 236 (2018), 183–202.
M. Ridwan, H. Assiyatun, E.T. Baskoro, The dominating partition dimension and locating-chromatic number of graphs, Electron. J. Graph Theory Appl. 11 (2) (2023), 455–465.
F. Harary and R.A. Melter,On the metric dimension of a graph, Ars Combin. 2 (1976), 191–195.
M. Jannesari, On doubly resolving sets in graphs, Bull. Malays. Math. Sci. Soc. 45 (2022), 2041–2052.
M. Jannesari, Graphs with constant adjacency dimension, Discrete Math. Algorithms Appl. 14 (04) (2022), 2150134 (9 pages).
M. Jannesari and B. Omoomi, The metric dimension of the lexicographic product of graphs, Discrete Math. 312 (22) (2012), 3349–3356.
J. Kratica, M. Čangalović, and V. Kovačević-Vujčić, Computing minimal doubly resolving sets of graphs , Computers & Operations Research 36 (7) (2009) 2149–2159.
J. Kratica, V. Kovačević-Vujčić, M. Čangalović, and M. Stojanović, Minimal doubly resolving sets and the strong metric dimension of Hamming graphs, Appl. Anal. Discrete Math. 6 (1) (2012), 63–71.
N. Mladenović, J. Kratica, V. Kovačević-Vujčić, and M. Čangalović, Variable neighborhood search for metric dimension and minimal doubly resolving set problems, European J. Oper. Res. 220 (12) (2012), 328–337.
I. Peterin and I.G. Yero, Edge metric dimension of some graph operations, Bull. Malays. Math. Sci. Soc. 43 (3) (2020), 2465–2477.
P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975), 549–559.
I.G. Yero, D. Kuziak and J.A. Rodríguez-Velázquez, On the metric dimension of corona product graphs, Computers and Mathematics with Applications 61 (2011), 2793–2798.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.