Algorithmic aspects of the k k -domination problem in graphs ?
For a positive integer k k , a k k -dominating set  of a graph G G is a subset D?V(G) D ? V ( G ) such that every vertex not in D D is adjacent to at least k k vertices in D D . The k k -domination problem  is to determine a minimum k k -dominating set of G G . This paper studies the k k -domination problem in graphs from an algorithmic point of view. In particular, we present a linear-time algorithm for the k k -domination problem for graphs in which each block is a clique, a cycle or a complete bipartite graph. This class of graphs includes trees, block graphs, cacti and block-cactus graphs. We also establish NP-completeness of the k k -domination problem in split graphs.
algorithm tree block graph block-cactus graph np-complete split graph k k -domination k k k k k cactus