Authors: Y.P. Deng, H.C. Wang, Y. Zhao Title: The complexity of secure domination problem in graphs Source: Discussiones Mathematicae Graph Theory Received 26.04.2016, Revised 09.11.2016, Accepted 01.12.2016, doi: 10.7151/dmgt.2008 | |
Abstract: 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 NP⊆DTIME(|V|^{O(\log\log|V|)}). Finally, we show that the secure domination problem is APX-complete for bounded degree graphs. | |
Keywords: secure domination, star convex bipartite graph, doubly chordal graph, NP-complete, APX-complete | |
Links: |