DMGT

For $k \geq 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\setminus 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 $\gamma_k(G)$. An ordered set of vertices $W=\{w_1,w_2,\ldots,w_r\}$ is a resolving set of $G$, if for any two distinct vertices $x$ and $y$ in $V\setminus W$, there exists $1\leq i\leq r$ such that $d_G(x,w_i)\neq d_G(y,w_i)$. The minimum cardinality of a resolving set of $G$ is the metric dimension of the graph $G$, denoted by $\dim(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 $\gamma^r_k(G)$. We give several bounds for $\gamma^r_k(G)$, some in terms of the metric dimension $\dim(G)$ and the distance $k$-domination number $\gamma_k(G)$. We determine $\gamma^r_k(G)$ when $G$ is a path or a cycle. Afterwards, we characterize the connected graphs of order $n$ having $\gamma^r_k(G)$ equal to $1$, $n-2$, and $n-1$, for $k\geq 2$. Then, we construct graphs realizing all the possible triples $(\dim(G),\gamma_k(G),\gamma^r_k (G))$, for all $k\geq 2$. Later, we determine the maximum order of a graph $G$ having distance $k$-resolving domination number $\gamma^r_k(G)=\gamma^r_k\geq 1$, we provide graphs achieving this maximum order for any positive integers $k$ and $\gamma^r_k$. Then, we establish Nordhaus-Gaddum bounds for $\gamma^r_k(G)$, for $k\geq 2$. Finally, we give relations between $\gamma^r_k(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

References:

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
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
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
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
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
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
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.
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
G. Chartrand, L. Lesniak and P. Zhang, Graphs & Digraphs, 6th Ed. (Chapman & Hall, London, 2016).
https://doi.org/10.1201/b19731
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
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
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
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
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
J. Geneson and E. Yi, The distance-k dimension of graphs (2021).
arXiv: 2106.08303v2
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
F. Harary and R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191–195.
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
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
M.A. Henning and O.R. Oellermann, Metric-locating-dominating sets in graphs, Ars Combin. 73 (2004) 129–141.
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.
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
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
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
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
D. Lichtenstein, Planar formulae and their uses, SIAM J. Comput. 11 (1982) 329–343.
https://doi.org/https://doi.org/10.1137/0211025
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
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
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
P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549–559.
P.J. Slater, $R$-domination in graphs, J. ACM 23 (1976) 446–450.
https://doi.org/10.1145/321958.321964
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
R.C. Tillquist, R.M. Frongillo and M.E. Lladser, Truncated metric dimension for finite graphs (2021).
arXiv: 2106.14314v1
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