A study of a combination of distance domination and resolvability in graphs

Retnowardani, Dwi Agustin ; Utoyo, Mohammad ; Dafik ; Susilowati, Liliek  ; Dliou, Kamal

Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 1051-1078

Résumé

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.

Détail

Keywords: resolving set, metric dimension, distance k-domination, distance k-resolving domination