ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 25(3) (2005) 291-302
DOI: 10.7151/dmgt.1282


Mustapha Chellali

Department of Mathematics, University of Blida
B.P. 270, Blida, Algeria

Abdelkader Khelladi

Department of Operations Research
Faculty of Mathematics
University of Sciences and Technology Houari Boumediene
B.P. 32, El Alia, Bab Ezzouar, Algiers, Algeria

Frédéric Maffray

C.N.R.S., Laboratoire Leibniz-IMAG
46 Avenue Félix Viallet
38031 Grenoble Cedex, France


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.

2000 Mathematics Subject Classification: 05C69.


[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).

Received 15 January 2004
Revised 8 November 2004