Double domination critical and stable graphs upon vertex removal

Soufiane Khelifi; Mustapha Chellali

Discussiones Mathematicae Graph Theory, Tome 32 (2012), p. 643-657 / Harvested from The Polish Digital Mathematics Library

Access to full text
Full (PDF)

Résumé

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 $γ_{\times 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 $γ_{\times 2}$ -vertex critical graph ( $γ_{\times 2}$ -vertex stable graph, respectively) if the removal of any vertex different from a support vertex decreases (does not change, respectively) $γ_{\times 2}$ (G). In this paper we investigate various properties of these graphs. Moreover, we characterize $γ_{\times 2}$ -vertex critical trees and $γ_{\times 2}$ -vertex stable trees.

Publié le : 2012-01-01

Zbl 1293.05266

EUDML-ID : urn:eudml:doc:271030

@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1633,
     author = {Soufiane Khelifi and Mustapha Chellali},
     title = {Double domination critical and stable graphs upon vertex removal},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {32},
     year = {2012},
     pages = {643-657},
     zbl = {1293.05266},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1633}
}

Soufiane Khelifi; Mustapha Chellali. Double domination critical and stable graphs upon vertex removal. Discussiones Mathematicae Graph Theory, Tome 32 (2012) pp. 643-657. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1633/

Bibliographie

[000] [1] M. Blidia, M. Chellali, T.W. Haynes and M. Henning, Independent and double domination in trees, Util. Math. 70 (2006) 159-173. | Zbl 1110.05074

[001] [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. | Zbl 1076.05058

[002] [3] G. Chartrand and L. Lesniak, Graphs and Digraphs: Fourth edition (Chapman and Hall/CRC Inc., Boca Raton, Fl., 2005). | Zbl 1057.05001

[003] [4] M. Chellali and T.W. Haynes, Double domination stable graphs upon edge removal, Australas. J. Combin. 47 (2010) 157-164. | Zbl 1218.05111

[004] [5] F. Harary and T.W. Haynes, Double domination in graphs, Ars Combin. 55 (2000) 201-213. | Zbl 0993.05104

[005] [6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998). | Zbl 0890.05002

[006] [7] S. Khelifi, M. Blidia, M. Chellali and F. Maffray, Double domination edge removal critical graphs, Australas. J. Combin. 48 (2010) 285-299. | Zbl 1232.05167