Geodesic
Exact double domination in graphs
Discussiones Mathematicae. Graph Theory, Tome 25 (2005) no. 3, pp. 291-302

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

In a graph a vertex is said to dominate itself and all its neighbours. A doubly dominating set of a graph G is a subset of vertices that dominates every vertex of G at least twice. A doubly dominating set is exact if every vertex of G is dominated exactly twice. We prove that the existence of an exact doubly dominating set is an NP-complete problem. We show that if an exact double dominating set exists then all such sets have the same size, and we establish bounds on this size. We give a constructive characterization of those trees that admit a doubly dominating set, and we establish a necessary and sufficient condition for the existence of an exact doubly dominating set in a connected cubic graph.
Keywords: double domination, exact double domination 
@article{DMGT_2005_25_3_a7,
     author = {Chellali, Mustapha and Khelladi, Abdelkader and Maffray, Fr\'ed\'eric},
     title = {Exact double domination in graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {291--302},
     publisher = {mathdoc},
     volume = {25},
     number = {3},
     year = {2005},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2005_25_3_a7/}
}
TY  - JOUR
AU  - Chellali, Mustapha
AU  - Khelladi, Abdelkader
AU  - Maffray, Frédéric
TI  - Exact double domination in graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2005
SP  - 291
EP  - 302
VL  - 25
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2005_25_3_a7/
LA  - en
ID  - DMGT_2005_25_3_a7
ER  - 
%0 Journal Article
%A Chellali, Mustapha
%A Khelladi, Abdelkader
%A Maffray, Frédéric
%T Exact double domination in graphs
%J Discussiones Mathematicae. Graph Theory
%D 2005
%P 291-302
%V 25
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2005_25_3_a7/
%G en
%F DMGT_2005_25_3_a7
Chellali, Mustapha; Khelladi, Abdelkader; Maffray, Frédéric. Exact double domination in graphs. Discussiones Mathematicae. Graph Theory, Tome 25 (2005) no. 3, pp. 291-302. http://geodesic.mathdoc.fr/item/DMGT_2005_25_3_a7/