Geodesic
The Complexity of Secure Domination Problem in Graphs
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 2, pp. 385-396

Voir la notice de l'article provenant de la source Library of Science

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) S has one neighbor v in S such that (S 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 ε gt; 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 
@article{DMGT_2018_38_2_a3,
     author = {Wang, Haichao and Zhao, Yancai and Deng, Yunping},
     title = {The {Complexity} of {Secure} {Domination} {Problem} in {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {385--396},
     publisher = {mathdoc},
     volume = {38},
     number = {2},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a3/}
}
TY  - JOUR
AU  - Wang, Haichao
AU  - Zhao, Yancai
AU  - Deng, Yunping
TI  - The Complexity of Secure Domination Problem in Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 385
EP  - 396
VL  - 38
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a3/
LA  - en
ID  - DMGT_2018_38_2_a3
ER  - 
%0 Journal Article
%A Wang, Haichao
%A Zhao, Yancai
%A Deng, Yunping
%T The Complexity of Secure Domination Problem in Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 385-396
%V 38
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a3/
%G en
%F DMGT_2018_38_2_a3
Wang, Haichao; Zhao, Yancai; Deng, Yunping. The Complexity of Secure Domination Problem in Graphs. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 2, pp. 385-396. http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a3/