# Exact double domination in graphs

Mustapha Chellali; Abdelkader Khelladi; Frédéric Maffray

Discussiones Mathematicae Graph Theory (2005)

- Volume: 25, Issue: 3, page 291-302
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topMustapha Chellali, Abdelkader Khelladi, and Frédéric Maffray. "Exact double domination in graphs." Discussiones Mathematicae Graph Theory 25.3 (2005): 291-302. <http://eudml.org/doc/270435>.

@article{MustaphaChellali2005,

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.},

author = {Mustapha Chellali, Abdelkader Khelladi, Frédéric Maffray},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {double domination; exact double domination; dominating set; NP-complete problem; polynomial time algorithm; cubic graph; tree},

language = {eng},

number = {3},

pages = {291-302},

title = {Exact double domination in graphs},

url = {http://eudml.org/doc/270435},

volume = {25},

year = {2005},

}

TY - JOUR

AU - Mustapha Chellali

AU - Abdelkader Khelladi

AU - Frédéric Maffray

TI - Exact double domination in graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2005

VL - 25

IS - 3

SP - 291

EP - 302

AB - 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.

LA - eng

KW - double domination; exact double domination; dominating set; NP-complete problem; polynomial time algorithm; cubic graph; tree

UR - http://eudml.org/doc/270435

ER -

## References

top- [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. Zbl0664.05027
- [2] M. Blidia, M. Chellali and T.W. Haynes, Characterizations of trees with equal paired and double domination numbers, submitted for publication. Zbl1100.05068
- [3] M. Blidia, M. Chellali, T.W. Haynes and M. Henning, Independent and double domination in trees, to appear in Utilitas Mathematica. Zbl1110.05074
- [4] M. Chellali and T.W. Haynes, On paired and double domination in graphs, to appear in Utilitas Mathematica. Zbl1069.05058
- [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. Zbl0531.05045
- [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). Zbl0411.68039
- [7] F. Harary and T.W. Haynes, Double domination in graphs, Ars Combin. 55 (2000) 201-213. Zbl0993.05104
- [8] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
- [9] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998). Zbl0883.00011

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.