Characterization of trees with equal 2-domination number and domination number plus two

Mustapha Chellali; Lutz Volkmann

Discussiones Mathematicae Graph Theory (2011)

  • Volume: 31, Issue: 4, page 687-697
  • ISSN: 2083-5892

Abstract

top
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 γₖ(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.

How to cite

top

Mustapha Chellali, and Lutz Volkmann. "Characterization of trees with equal 2-domination number and domination number plus two." Discussiones Mathematicae Graph Theory 31.4 (2011): 687-697. <http://eudml.org/doc/270882>.

@article{MustaphaChellali2011,
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 γₖ(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.},
author = {Mustapha Chellali, Lutz Volkmann},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {2-domination number; domination number; trees},
language = {eng},
number = {4},
pages = {687-697},
title = {Characterization of trees with equal 2-domination number and domination number plus two},
url = {http://eudml.org/doc/270882},
volume = {31},
year = {2011},
}

TY - JOUR
AU - Mustapha Chellali
AU - Lutz Volkmann
TI - Characterization of trees with equal 2-domination number and domination number plus two
JO - Discussiones Mathematicae Graph Theory
PY - 2011
VL - 31
IS - 4
SP - 687
EP - 697
AB - 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 γₖ(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.
LA - eng
KW - 2-domination number; domination number; trees
UR - http://eudml.org/doc/270882
ER -

References

top
  1. [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. Zbl1207.05136
  2. [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. Zbl0573.05049
  3. [3] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs ( Marcel Dekker, Inc., New York, 1998). Zbl0890.05002
  4. [4] S.M. Hedetniemi, S.T. Hedetniemi, and P. Kristiansen, Alliances in graphs, J. Combin. Math. Combin. Comput. 48 (2004) 157-177. Zbl1051.05068
  5. [5] L. Volkmann, Some remarks on lower bounds on the p-domination number in trees, J. Combin. Math. Combin. Comput. 61 (2007) 159-167. Zbl1137.05055

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.