Perfect k-domination in graphs

Abstract

Let k be a positive integer. A vertex subset D of a graph G =(V,E) is a perfect k-dominating set of G if every vertex v of G, not in D, is adjacent to exactly k vertices of D. The minimum cardinality of a perfect k-dominating set of G is the perfect k-domination number γkp(G). In this paper, we generalize perfect domination to perfect k-domination, where many bounds of γkp(G) are obtained. We prove that the perfect k-domination problem is NP-complete for general graphs.