Algorithmic aspects of the k-domination problem in graphs

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