A study of a combination of distance domination and resolvability in graphs
Dwi Agustin Retnowardani, Mohammad Imam Utoyo, Dafik Dafik, Liliek Susilowati, Kamal Dliou · Discussiones Mathematicae Graph Theory · 2023
For k ≥ 1, in a graph G = (V, E), a set of vertices D is a distance kdominating 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 2 D.A. Retnowardani, M.I.Utoyo, Dafik, L. Susilowati and K. Dliou two distinct vertices x and y in V \ W , there exists 1The 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 γ r k (G).We give several bounds for γ r k (G), some in terms of the metric dimension dim(G) and the distance k-domination number γ k (G).We determine γ r k (G) when G is a path or a cycle.Afterwards, we characterize the connected graphs of order n having γ r k (G) equal to 1, n -2, and n -1, for k ≥ 2.Then, we construct graphs realizing all the possible triples (dim(G), γ k (G), γ r k (G)), for all k ≥ 2. Later, we determine the maximum order of a graph G having distance k-resolving domination number γ r k (G) = γ r k ≥ 1, we provide graphs achieving this maximum order for any positive integers k and γ r k .Then, we establish Nordhaus-Gaddum bounds for γ r k (G), for k ≥ 2. Finally, we give relations between γ r k (G) and the k-truncated metric dimension of graphs and give some directions for future work.