# Double domination critical and stable graphs upon vertex removal

Soufiane Khelifi; Mustapha Chellali

Discussiones Mathematicae Graph Theory (2012)

- Volume: 32, Issue: 4, page 643-657
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topSoufiane Khelifi, and Mustapha Chellali. "Double domination critical and stable graphs upon vertex removal." Discussiones Mathematicae Graph Theory 32.4 (2012): 643-657. <http://eudml.org/doc/271030>.

@article{SoufianeKhelifi2012,

abstract = {In a graph a vertex is said to dominate itself and all its neighbors. A double dominating set of a graph G is a subset of vertices that dominates every vertex of G at least twice. The double domination number of G, denoted $γ_\{×2\}(G)$, is the minimum cardinality among all double dominating sets of G. We consider the effects of vertex removal on the double domination number of a graph. A graph G is $γ_\{×2\}$-vertex critical graph ($γ_\{×2\}$-vertex stable graph, respectively) if the removal of any vertex different from a support vertex decreases (does not change, respectively) $γ_\{×2\}$(G). In this paper we investigate various properties of these graphs. Moreover, we characterize $γ_\{×2\}$-vertex critical trees and $γ_\{×2\}$-vertex stable trees.},

author = {Soufiane Khelifi, Mustapha Chellali},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {double domination; vertex removal critical graphs; vertex removal stable graphs},

language = {eng},

number = {4},

pages = {643-657},

title = {Double domination critical and stable graphs upon vertex removal},

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

volume = {32},

year = {2012},

}

TY - JOUR

AU - Soufiane Khelifi

AU - Mustapha Chellali

TI - Double domination critical and stable graphs upon vertex removal

JO - Discussiones Mathematicae Graph Theory

PY - 2012

VL - 32

IS - 4

SP - 643

EP - 657

AB - In a graph a vertex is said to dominate itself and all its neighbors. A double dominating set of a graph G is a subset of vertices that dominates every vertex of G at least twice. The double domination number of G, denoted $γ_{×2}(G)$, is the minimum cardinality among all double dominating sets of G. We consider the effects of vertex removal on the double domination number of a graph. A graph G is $γ_{×2}$-vertex critical graph ($γ_{×2}$-vertex stable graph, respectively) if the removal of any vertex different from a support vertex decreases (does not change, respectively) $γ_{×2}$(G). In this paper we investigate various properties of these graphs. Moreover, we characterize $γ_{×2}$-vertex critical trees and $γ_{×2}$-vertex stable trees.

LA - eng

KW - double domination; vertex removal critical graphs; vertex removal stable graphs

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

ER -

## References

top- [1] M. Blidia, M. Chellali, T.W. Haynes and M. Henning, Independent and double domination in trees, Util. Math. 70 (2006) 159-173. Zbl1110.05074
- [2] M. Blidia, M. Chellali and S. Khelifi, Vertices belonging to all or to no minimum double domination sets of trees, AKCE Int. J. Graphs Comb. 2(1) (2005) 1-9. Zbl1076.05058
- [3] G. Chartrand and L. Lesniak, Graphs and Digraphs: Fourth edition (Chapman and Hall/CRC Inc., Boca Raton, Fl., 2005). Zbl1057.05001
- [4] M. Chellali and T.W. Haynes, Double domination stable graphs upon edge removal, Australas. J. Combin. 47 (2010) 157-164. Zbl1218.05111
- [5] F. Harary and T.W. Haynes, Double domination in graphs, Ars Combin. 55 (2000) 201-213. Zbl0993.05104
- [6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998). Zbl0890.05002
- [7] S. Khelifi, M. Blidia, M. Chellali and F. Maffray, Double domination edge removal critical graphs, Australas. J. Combin. 48 (2010) 285-299. Zbl1232.05167

## NotesEmbed ?

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