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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1282,
author = {Mustapha Chellali and Abdelkader Khelladi and Fr\'ed\'eric Maffray},
title = {Exact double domination in graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {25},
year = {2005},
pages = {291-302},
zbl = {1106.05071},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1282}
}
Mustapha Chellali; Abdelkader Khelladi; Frédéric Maffray. Exact double domination in graphs. Discussiones Mathematicae Graph Theory, Tome 25 (2005) pp. 291-302. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1282/
[000] [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. | Zbl 0664.05027
[001] [2] M. Blidia, M. Chellali and T.W. Haynes, Characterizations of trees with equal paired and double domination numbers, submitted for publication. | Zbl 1100.05068
[002] [3] M. Blidia, M. Chellali, T.W. Haynes and M. Henning, Independent and double domination in trees, to appear in Utilitas Mathematica. | Zbl 1110.05074
[003] [4] M. Chellali and T.W. Haynes, On paired and double domination in graphs, to appear in Utilitas Mathematica. | Zbl 1069.05058
[004] [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. | Zbl 0531.05045
[005] [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). | Zbl 0411.68039
[006] [7] F. Harary and T.W. Haynes, Double domination in graphs, Ars Combin. 55 (2000) 201-213. | Zbl 0993.05104
[007] [8] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). | Zbl 0890.05002
[008] [9] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998). | Zbl 0883.00011