The complexity of the defensive domination problem in special graph classes

TitleThe complexity of the defensive domination problem in special graph classes
Publication TypeJournal Article
Year of Publication2020
AuthorsEkim, T., A. M. Farley, and A. Proskurowski
JournalDiscrete Mathematics
Volume343
Pagination111665
ISSN0012-365X
KeywordsDomination, Networks, Security
Abstract

A k-attack on a graph G is a set of k distinct vertices {a1,…,ak} which are said to be under attack. A k-attack A can be countered or defended by a subset of defender vertices X if and only if there exists an injective function f from A to X, such that either f(ai)=ai or (ai,f(ai)) is an edge of G, for all i, 1≤i≤k. Given a graph G, a subset D of V is a k-defensive dominating set of G if and only if D can counter any k-attack in G. We consider the k-defensive dominating set problem. We start a systematic study on the complexity of the k-defensive dominating set problem. When k is not fixed, we show that it is already co-NP-hard to decide whether a given set of vertices is a k-defensive dominating set or not. However, if k is fixed, then we show that the problem is NP-complete even in split graphs. Subsequently, we consider special graph classes, namely paths, cycles, co-chain graphs and threshold graphs. We show that in each of these graph classes, a k-defensive dominating set of minimum size can be found in linear time even for non-fixed k.

URLhttps://www.sciencedirect.com/science/article/pii/S0012365X19303437
DOI10.1016/j.disc.2019.111665