Algorithmic aspects of the kk-domination problem in graphs

For a positive integer kk, a kk-dominating set   of a graph GG is a subset D⊆V(G)D⊆V(G) such that every vertex not in DD is adjacent to at least kk vertices in DD. The kk-domination problem   is to determine a minimum kk-dominating set of GG. This paper studies the kk-domination problem in graphs from an algorithmic point of view. In particular, we present a linear-time algorithm for the kk-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 kk-domination problem in split graphs.