On the integrity of distance domination in graphs.
Timothy Jackson. Bean, Michael A. Henning, Henda C. Swart · 1994
Let n and k be positive integers and let G be a graph. A set D of vertices of G is defined to be an (n, k)-dominating set of G if every vertex of V ( G) D is within distance n from at least k vertices of D. The minimum cardinality among all (n, k)-dominating sets of G is called the (n, k)-domination number of G and is denoted by 'Yn,k(G). A set I of vertices of G is defined to be an (n, k)-independent set in G if every vertex of I is within distance n from at most k-1 other vertices of I in G. We denote by f3n,k ( G) the maximum cardinality of an (n, k)-independent set of G. We show that the problem of computing 'Yn,k is in the NP-complete class, even when restricted to bipartite graphs and chordal graphs. We prove that in every graph there exist some subsets of vertices that are both (n, k)-independent and (n, k)-dominating, so In,k:s; f3n,k ' We also investigate lower and upper bounds on 'Yn,k'