Y.P. Deng, H.C. Wang, Y. Zhao
The complexity of secure domination problem in graphs
Discussiones Mathematicae Graph Theory
Received 26.04.2016, Revised 09.11.2016, Accepted 01.12.2016, doi: 10.7151/dmgt.2008

A dominating set of a graph G is a subset D⊆ V(G) such that every vertex not in D is adjacent to at least one vertex in D. A dominating set S of G is called a secure dominating set if each vertex u∈V(G)\setminus S has one neighbor v in S such that (S\setminus{v})∪{u} is a dominating set of G. The secure domination problem is to determine a minimum secure dominating set of G. In this paper, we first show that the decision version of the secure domination problem is NP-complete for star convex bipartite graphs and doubly chordal graphs. We also prove that the secure domination problem cannot be approximated within a factor of (1-ϵ)\ln|V| for any ϵ>0, unless NPDTIME(|V|O(\log\log|V|)). Finally, we show that the secure domination problem is APX-complete for bounded degree graphs.
secure domination, star convex bipartite graph, doubly chordal graph, NP-complete, APX-complete