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/

[1] D.W. Bange, A.E. Barkauskas and P.J. Slater, Efficient dominating sets in graphs, in: Applications of Discrete Mathematics, R.D. Ringeisen and F.S. Roberts, eds (SIAM, Philadelphia, 1988) 189-199.

[2] M. Blidia, M. Chellali and T.W. Haynes, Characterizations of trees with equal paired and double domination numbers, submitted for publication.

[3] M. Blidia, M. Chellali, T.W. Haynes and M. Henning, Independent and double domination in trees, to appear in Utilitas Mathematica.

[4] M. Chellali and T.W. Haynes, On paired and double domination in graphs, to appear in Utilitas Mathematica.

[5] M. Farber, Domination, independent domination and duality in strongly chordal graphs, Discrete Appl. Math. 7 (1984) 115-130, doi: 10.1016/0166-218X(84)90061-1.

[6] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness (W.H. Freeman, San Francisco, 1979).

[7] F. Harary and T.W. Haynes, Double domination in graphs, Ars Combin. 55 (2000) 201-213.

[8] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).

[9] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998).