THE K-NEIGHBOR DOMINATION PROBLEM

Abstract

As a model of certain location problem, we 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, we also prove that the k-neighbor domination problem is NP-complete for some classes of graphs.