Double domination critical and stable graphs upon vertex removal

• Autorzy: Soufiane Khelifi , Mustapha Chellali
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

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

Kategorie tematyczne

• 05C69: Dominating sets, independent sets, cliques

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2012
• Tom: 32
• Numer: 4
• Strony: 643-657

Daty

wydano

2012

otrzymano

2011-05-20

poprawiono

2011-11-25

zaakceptowano

2011-11-30

Twórcy

autor

Soufiane Khelifi

• Laboratory LMP2M, Bloc of laboratories University of MEDEA, Ain D'heb 26000 MEDEA, Algeria

autor

Mustapha Chellali

• LAMDA-RO, Department of Mathematics, University of Blida, B. P. 270, Blida, Algeria

Bibliografia

• [1] M. Blidia, M. Chellali, T.W. Haynes and M. Henning, Independent and double domination in trees, Util. Math. 70 (2006) 159-173.
• [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.
• [3] G. Chartrand and L. Lesniak, Graphs and Digraphs: Fourth edition (Chapman and Hall/CRC Inc., Boca Raton, Fl., 2005).
• [4] M. Chellali and T.W. Haynes, Double domination stable graphs upon edge removal, Australas. J. Combin. 47 (2010) 157-164.
• [5] F. Harary and T.W. Haynes, Double domination in graphs, Ars Combin. 55 (2000) 201-213.
• [6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998).
• [7] S. Khelifi, M. Blidia, M. Chellali and F. Maffray, Double domination edge removal critical graphs, Australas. J. Combin. 48 (2010) 285-299.

Identyfikatory

DOI

10.7151/dmgt.1633