PDF

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

EXACT DOUBLE DOMINATION IN GRAPHS

Mustapha Chellali Department of Mathematics, University of Blida B.P. 270, Blida, Algeria e-mail: mchellali@hotmail.com

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 e-mail: kader_khelladi@yahoo.fr

Frédéric Maffray C.N.R.S., Laboratoire Leibniz-IMAG 46 Avenue Félix Viallet 38031 Grenoble Cedex, France e-mail: frederic.maffray@imag.fr

Abstract

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.

References

[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