On d-distance m-tuple (l, r)-domination in graphs

In this article, we study the d-distance m-tuple (l, r)-domination problem. Given a simple undirected graph G = (V, E), and positive integers d, m, l and r, a subset V' subset of V is said to be a d-distance m-tuple (l, r)-dominating set if it satisfies the following conditions: (i) each vertex v is an element of V is d-distance dominated by at least m vertices in V', and (ii) each r size subset U of V is d-distance dominated by at least l vertices in V'. Here, a vertex vis d-distance dominated by another vertex u means the shortest path distance between u and vis at most d in G. A set U is d-distance dominated by a set of l vertices means size of the union of the d-distance neighborhood of all vertices of U in V' is at least l. The objective of the d-distance m-tuple (l, r)-domination problem is to find a minimum size subset V' subset of V satisfying the above two conditions. We prove that the problem of deciding whether a graph G has (i) a 1-distance m-tuple (l, r)-dominating set for each fixed value of m, l, and r, and (ii) a d-distance m-tuple (l, 2)-dominating set for each fixed value of d(>= 2), m, and l of cardinality at most k (here k is a positive integer) are NP-complete. We also prove that for any epsilon > 0, the 1-distance m-tuple (l, r)-domination problem and the d-distance m-tuple (l, 2)-domination problem cannot be approximated within a factor of (1/2 - epsilon) ln vertical bar V vertical bar and (1/4 - epsilon) ln vertical bar V vertical bar, respectively, unless P = NP. (C) 2021 Elsevier B.V. All rights reserved.