PDF

Discussiones Mathematicae Graph Theory 31(4) (2011) 687-697
DOI: https://doi.org/10.7151/dmgt.1573

Characterization of Trees with Equal 2-domination Number and domination number plus two

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

Lutz Volkmann Lehrstuhl II für Mathematik RWTH Aachen University, Templergraben 55, D--52056 Aachen, Germany

Abstract

Let G = (V(G),E(G)) be a simple graph, and let k be a positive integer. A subset D of V(G) is a k-dominating set if every vertex of V(G) −D is dominated at least k times by D. The k-domination number γ_k(G) is the minimum cardinality of a k-dominating set of G. In [5] Volkmann showed that for every nontrivial tree T, γ₂(T) ≥ γ₁(T)+1 and characterized extremal trees attaining this bound. In this paper we characterize all trees T with γ₂(T) = γ₁(T)+2.

Keywords: 2-domination number, domination number, trees

2010 Mathematics Subject Classification: 05C69.

References

[1]	M. Chellali, T.W. Haynes and L. Volkmann, Global offensive alliance numbers in graphs with emphasis on trees, Australasian J. Combin. 45 (2009) 87--96.
[2]	J.F. Fink and M.S. Jacobson, n-domination in graphs, in: Y. Alavi and A.J. Schwenk, editors, ed(s), Graph Theory with Applications to Algorithms and Computer Science (Wiley, New York, 1985) 283--300.
[3]	T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs ( Marcel Dekker, Inc., New York , 1998).
[4]	S.M. Hedetniemi, S.T. Hedetniemi, and P. Kristiansen, Alliances in graphs, J. Combin. Math. Combin. Comput. 48 (2004) 157--177.
[5]	L. Volkmann, Some remarks on lower bounds on the p-domination number in trees, J. Combin. Math. Combin. Comput. 61 (2007) 159--167.

Received 30 March 2010
Revised 25 October 2010
Accepted 25 October 2010