The k-neighbor domination problem
Journal
European Journal of Operational Research
Journal Volume
52
Journal Issue
3
Pages
373-377
Date Issued
1991
Author(s)
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. © 1991.
SDGs
Type
journal article