| Popis: |
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 ′ ⊆ V is said to be a d-distance m-tuple ( l , r )-dominating set if it satisfies the following conditions: (i) each vertex v ∈ 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 v is d-distance dominated by another vertex u means the shortest path distance between u and v is 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 ′ ⊆ 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 e > 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 − e ) ln | V | and ( 1 4 − e ) ln | V | , respectively, unless P = N P . |
