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

Abstract

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

How to cite

top

Mustapha 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. [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. [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. [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. [4] M. Chellali and T.W. Haynes, On paired and double domination in graphs, to appear in Utilitas Mathematica. Zbl1069.05058
  5. [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. [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. [7] F. Harary and T.W. Haynes, Double domination in graphs, Ars Combin. 55 (2000) 201-213. Zbl0993.05104
  8. [8] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
  9. [9] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998). Zbl0883.00011

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.