On k-dependent domination

A k-dependent dominating set D in a graph G=(V,E) is a set which is both k-dependent and dominating, where a set is k-dependent if the maximum degree of a vertex in the subgraph 〈D〉 induced by D is at most k, and a set D is dominating if every vertex not in D is adjacent to at least one vertex in D. This paper introduces the concept of k-dependent domination and establishes close relationships between k-dependent domination and the standard concepts of domination and irredundance in graphs. Computational complexity questions corresponding to the decision problems associated with k-dependent dominating sets and k-dependent irredundant sets are also answered.