The complexity of the defensive domination problem in special graph classes
Discrete Mathematics, cilt.343, sa.2, 2020 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 343 Sayı: 2
- Basım Tarihi: 2020
- Doi Numarası: 10.1016/j.disc.2019.111665
- Dergi Adı: Discrete Mathematics
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Applied Science & Technology Source, Computer & Applied Sciences, MathSciNet, zbMATH
- Anahtar Kelimeler: Domination, Networks, Security
- Boğaziçi Üniversitesi Adresli: Evet
Özet
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.