The k-neighbor domination problem

As a model of certain location problem, the authors consider the following domination problem. The k-neighbor domination problem is to select a minimum cardinality vertex set D of a graph G=(V,E) such that every vertex x not in D is adjacent to at least k vertices in D. This paper presents a linear algorithm to solve the problem for block graphs. For any fixed k, the authors also prove that the k-neighbor domination problem is NP-complete for some classes of graphs.