Geodesic
A study of a combination of distance domination and resolvability in graphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 1051-1078 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

For k ≥ 1, in a graph G=(V,E), a set of vertices D is a distance k-dominating set of G, if any vertex in V∖ D is at distance at most k from some vertex in D. The minimum cardinality of a distance k-dominating set of G is the distance k-domination number, denoted by γ_k(G). An ordered set of vertices W={w_1,w_2,…,w_r} is a resolving set of G, if for any two distinct vertices x and y in V∖ W, there exists 1≤ i≤ r such that d_G(x,w_i) d_G(y,w_i). The minimum cardinality of a resolving set of G is the metric dimension of the graph G, denoted by (G). In this paper, we introduce the distance k-resolving dominating set which is a subset of V that is both a distance k-dominating set and a resolving set of G. The minimum cardinality of a distance k-resolving dominating set of G is called the distance k-resolving domination number and is denoted by γ_k^r (G). We give several bounds for γ_k^r(G), some in terms of the metric dimension (G) and the distance k-domination number γ_k(G). We determine γ_k^r(G) when G is a path or a cycle. Afterwards, we characterize the connected graphs of order n having γ_k^r (G) equal to 1, n-2, and n-1, for k≥ 2. Then, we construct graphs realizing all the possible triples ((G),γ_k(G),γ_k^r (G)), for all k≥ 2. Later, we determine the maximum order of a graph G having distance k-resolving domination number γ_k^r(G)=γ_k^r ≥ 1, we provide graphs achieving this maximum order for any positive integers k and γ_k^r. Then, we establish Nordhaus-Gaddum bounds for γ_k^r (G), for k≥ 2. Finally, we give relations between γ_k^r(G) and the k-truncated metric dimension of graphs and give some directions for future work.
Keywords: resolving set, metric dimension, distance k-domination, distance k-resolving domination 
@article{DMGT_2024_44_3_a13,
     author = {Retnowardani, Dwi Agustin and Utoyo, Mohammad and Dafik and Susilowati, Liliek and Dliou, Kamal},
     title = {A study of a combination of distance domination and resolvability in graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1051--1078},
     year = {2024},
     volume = {44},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a13/}
}
TY  - JOUR
AU  - Retnowardani, Dwi Agustin
AU  - Utoyo, Mohammad
AU  - Dafik
AU  - Susilowati, Liliek
AU  - Dliou, Kamal
TI  - A study of a combination of distance domination and resolvability in graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 1051
EP  - 1078
VL  - 44
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a13/
LA  - en
ID  - DMGT_2024_44_3_a13
ER  - 
%0 Journal Article
%A Retnowardani, Dwi Agustin
%A Utoyo, Mohammad
%A Dafik
%A Susilowati, Liliek
%A Dliou, Kamal
%T A study of a combination of distance domination and resolvability in graphs
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 1051-1078
%V 44
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a13/
%G en
%F DMGT_2024_44_3_a13
Retnowardani, Dwi Agustin; Utoyo, Mohammad; Dafik; Susilowati, Liliek; Dliou, Kamal. A study of a combination of distance domination and resolvability in graphs. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 1051-1078. http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a13/

[1] M. Aouchiche and P. Hansen, A survey of Nordhaus-Gaddum type relations, Discrete Appl. Math. 161 (2013) 466-546. https://doi.org/10.1016/j.dam.2011.12.018

[2] R.F. Bailey and P.J. Cameron, Base size, metric dimension and other invariants of groups and graphs, Bull. Lond. Math. Soc. 43 (2011) 209–242. https://doi.org/10.1112/blms/bdq096

[3] Z. Beerliova, F. Eberhard, T. Eberhard, A. Hall, M. Hoffmann, M. Mihalák and L.S. Ram, Network discovery and verification, IEEE J. Sel. Areas Commun. 24 (2006) 2168–2181. https://doi.org/10.1109/JSAC.2006.884015

[4] R.C. Brigham, G. Chartrand, R.D. Dutton and P. Zhang, Resolving domination in graphs, Math. Bohem. 128 (2003) 25–36. https://doi.org/10.21136/MB.2003.133935

[5] J. Cáceres, C. Hernando, M. Mora, I.M. Pelayo and M.L. Puertas, Locating-dominating codes: Bounds and extremal cardinalities, Appl. Math. Comput. 220 (2013) 38–45. https://doi.org/10.1016/j.amc.2013.05.060

[6] 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 (2007) 423–441. https://doi.org/10.1137/050641867

[7] G.J. Chang and G.L. Nemhauser, The k-domination and k-stability problem on graphs, Tech. Rep. 540 (School of Operations Res. and Industrial Eng., Cornell Univ., 1982) 332–345.

[8] G. Chartrand, L. Eroh, M.A. Jhonson and O.R. Oellermann, Resolvability in graphs and the metric dimenson of a graph, Discrete Appl. Math. 105 (2000) 99–113. https://doi.org/10.1016/S0166-218X(00)00198-0

[9] G. Chartrand, L. Lesniak and P. Zhang, Graphs & Digraphs, 6th Ed. (Chapman & Hall, London, 2016). https://doi.org/10.1201/b19731

[10] G. Chartrand, C. Poisson and P. Zhang, Resolvability and the upper dimension of graphs, Comput. Math. Appl. 39 (2000) 19–28. https://doi.org/10.1016/S0898-1221(00)00126-7

[11] G. Chartrand, V. Saenpholphat and P. Zhang, The independent resolving number of a graph, Math. Bohem. 128 (2003) 379–393. https://doi.org/10.21136/MB.2003.134003

[12] R.R. Davila, C. Fast, M.A. Henning and F. Kenter, Lower bounds on the distance domination number of a graph, Contrib. Discrete Math. 12 (2017). https://doi.org/10.11575/cdm.v12i2.62487

[13] A. Estrada-Moreno, I.G. Yero and J.A. Rodríguez-Velázquez, On the (k,t)-metric dimension of graphs, Comput. J. 64 (2021) 707–720. https://doi.org/10.1093/comjnl/bxaa009

[14] R.M. Frongillo, J. Geneson, M.E. Lladser, R.C. Tillquist and E. Yi, Truncated metric dimension for finite graphs, Discrete Appl. Math. 320 (2022) 150–169. https://doi.org/10.1016/j.dam.2022.04.021

[15] J. Geneson and E. Yi, The distance-k dimension of graphs (2021). arXiv: 2106.08303v2

[16] A. González, C. Hernando and M. Mora, Metric-locating-dominating sets of graphs for constructing related subsets of vertices, Appl. Math. Comput. 332 (2018) 449–456. https://doi.org/10.1016/j.amc.2018.03.053

[17] F. Harary and R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191–195.

[18] M.A. Henning, Distance domination in graphs, in: Topics in Domination in Graphs, T.W. Haynes, S.T. Hedetniemi and M.A. Henning (Ed(s)), (Springer, Cham 2020) 205–250. https://doi.org/10.1007/978-3-030-51117-3\_7

[19] M.A. Henning, Distance domination in graphs, in: Domination in Graphs: Advanced Topics, T.W. Haynes, S.T. Hedetniemi, and P.J. Slater (Ed(s)), (Marcel Dekker, Inc. New York 1998) 321–349. https://doi.org/10.1201/9781315141428

[20] M.A. Henning and O.R. Oellermann, Metric-locating-dominating sets in graphs, Ars Combin. 73 (2004) 129–141.

[21] M.A. Henning, O.R. Oellermann and H.C. Swart, Relating pairs of distance domination parameters, J. Combin. Math. Combin. Comput. 18 (1995) 233–244.

[22] C. Hernando, M. Mora and I.M. Pelayo, Nordhaus-Gaddum bound for locating domination, European J. Combin. 36 (2014) 1–6. https://doi.org/10.1016/j.ejc.2013.04.009

[23] C. Hernando, M. Mora, I.M. Pelayo, C. Seara and D.R. Wood, Extremal graph theory for metric dimension and diameter, Electron. J. Combin. 17 (2010) #R30. https://doi.org/10.37236/302

[24] M. Jannesari and B. Omoomi, The metric dimension of the lexicographic product of graphs, Discrete Math 312 (2012) 3349–3356. https://doi.org/10.1016/j.disc.2012.07.025

[25] S. Khuller, B. Raghavachari and A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70 (1996) 217–229. https://doi.org/10.1016/0166-218X(95)00106-2

[26] D. Lichtenstein, Planar formulae and their uses, SIAM J. Comput. 11 (1982) 329–343. https://doi.org/https://doi.org/10.1137/0211025

[27] A. Lobstein, O. Hudry and I. Charon, Locating-domination and identification, in: Topics in Domination in Graphs, T.W. Haynes, S.T. Hedetniemi and M.A. Henning (Ed(s)), (Springer, Cham 2020) 251–299. https://doi.org/10.1007/978-3-030-51117-3\_8

[28] A. Meir and J.W. Moon, Relations between packing and covering numbers of a tree, Pacific J. Math. 61(1) (1975) 225–233. https://doi.org/10.2140/pjm.1975.61.225

[29] V. Saenpholphat and P. Zhang, Connected resolvability of graphs, Czechoslovak Math. J. 53 (2003) 827–840. https://doi.org/10.1023/B:CMAJ.0000024524.43125.cd

[30] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549–559.

[31] P.J. Slater, R-domination in graphs, J. ACM 23 (1976) 446–450. https://doi.org/10.1145/321958.321964

[32] R.C. Tillquist, R.M. Frongillo and M.E. Lladser, Getting the lay of the land in discrete space: A survey of metric dimension and its applications (2021). arXiv: 2104.07201

[33] R.C. Tillquist, R.M. Frongillo and M.E. Lladser, Truncated metric dimension for finite graphs (2021). arXiv: 2106.14314v1

[34] D.A.R. Wardani, M.I. Utoyo, Dafik and K. Dliou, The distance 2-resolving domination number of graphs, J. Phys. Conf. Ser. 1836 (2021) 012017. https://doi.org/10.1088/1742-6596/1836/1/012017