A STUDY OF A COMBINATION OF DISTANCE DOMINATION AND RESOLVABILITY IN GRAPHS

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 = {w1,w2, . . . ,wr} 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 dG(x,wi)≠ dG(y,wi). The minimum cardinality of a resolving set of G is the metric γkension of the graph G, denoted by γk(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 γkension γk(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 (γk(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 γkension of graphs and give some directions for future work.