Discussiones Mathematicae Graph Theory 32(4) (2012) 643-657
doi: 10.7151/dmgt.1633

[BIBTex] [PDF] [PS]

Double domination critical and stable graphs upon vertex removal

Soufiane Khelifi

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

Mustapha Chellali

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


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.

Keywords: double domination, vertex removal critical graphs, vertex removal stable graphs.

2010 Mathematics Subject Classification: 05C69.


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

Received 20 May 2011
Revised 25 November 2011
Accepted 30 November 2011