An inequality chain of domination parameters for trees

E.J. Cockayne; O. Favaron; J. Puech; C.M. Mynhardt

Discussiones Mathematicae Graph Theory (1998)

  • Volume: 18, Issue: 1, page 127-142
  • ISSN: 2083-5892

Abstract

top
We prove that the smallest cardinality of a maximal packing in any tree is at most the cardinality of an R-annihilated set. As a corollary to this result we point out that a set of parameters of trees involving packing, perfect neighbourhood, R-annihilated, irredundant and dominating sets is totally ordered. The class of trees for which all these parameters are equal is described and we give an example of a tree in which most of them are distinct.

How to cite

top

E.J. Cockayne, et al. "An inequality chain of domination parameters for trees." Discussiones Mathematicae Graph Theory 18.1 (1998): 127-142. <http://eudml.org/doc/270420>.

@article{E1998,
abstract = {We prove that the smallest cardinality of a maximal packing in any tree is at most the cardinality of an R-annihilated set. As a corollary to this result we point out that a set of parameters of trees involving packing, perfect neighbourhood, R-annihilated, irredundant and dominating sets is totally ordered. The class of trees for which all these parameters are equal is described and we give an example of a tree in which most of them are distinct.},
author = {E.J. Cockayne, O. Favaron, J. Puech, C.M. Mynhardt},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {domination; irredundance; packing; perfect neighbourhoods; annihilation; tree},
language = {eng},
number = {1},
pages = {127-142},
title = {An inequality chain of domination parameters for trees},
url = {http://eudml.org/doc/270420},
volume = {18},
year = {1998},
}

TY - JOUR
AU - E.J. Cockayne
AU - O. Favaron
AU - J. Puech
AU - C.M. Mynhardt
TI - An inequality chain of domination parameters for trees
JO - Discussiones Mathematicae Graph Theory
PY - 1998
VL - 18
IS - 1
SP - 127
EP - 142
AB - We prove that the smallest cardinality of a maximal packing in any tree is at most the cardinality of an R-annihilated set. As a corollary to this result we point out that a set of parameters of trees involving packing, perfect neighbourhood, R-annihilated, irredundant and dominating sets is totally ordered. The class of trees for which all these parameters are equal is described and we give an example of a tree in which most of them are distinct.
LA - eng
KW - domination; irredundance; packing; perfect neighbourhoods; annihilation; tree
UR - http://eudml.org/doc/270420
ER -

References

top
  1. [1] E.J. Cockayne, O. Favaron, C.M. Mynhardt and J. Puech, A characterisation of (γ,i)-trees, (preprint). Zbl0949.05059
  2. [2] E.J. Cockayne, O. Favaron, C.M. Mynhardt and J. Puech, Packing, perfect neighbourhood, irredundant and R-annihilated sets in graphs, Austr. J. Combin. Math. (to appear). Zbl0916.05042
  3. [3] E.J. Cockayne, P.J. Grobler, S.T. Hedetniemi and A.A. McRae, What makes an irredundant set maximal?, J. Combin. Math. Combin. Comput. (to appear). Zbl0907.05032
  4. [4] E.J. Cockayne, J.H. Hattingh, S.M. Hedetniemi, S.T. Hedetniemi and A.A. McRae, Using maximality and minimality conditions to construct inequality chains, Discrete Math. 176 (1997) 43-61, doi: 10.1016/S0012-365X(96)00356-1. Zbl0887.05031
  5. [5] E.J. Cockayne, S.M. Hedetniemi, S.T. Hedetniemi and C.M. Mynhardt, Irredundant and perfect neighbourhood sets in trees, Discrete Math. (to appear). Zbl0955.05027
  6. [6] E.J. Cockayne and C.M. Mynhardt, On a conjecture concerning irredundant and perfect neighbourhood sets in graphs, J. Combin. Math. Combin. Comput. (to appear). Zbl0949.05060
  7. [7] O. Favaron and J. Puech, Irredundant and perfect neighbourhood sets in graphs and claw-free graphs, Discrete Math. (to appear). Zbl0957.05081
  8. [8] G.H. Fricke, T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi and M.A. Henning, Perfect neighborhoods in graphs, (preprint). 
  9. [9] B.L. Hartnell, On maximal radius two independent sets, Congr. Numer. 48 (1985) 179-182. 
  10. [10] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs (Marcel Dekker, 1997). Zbl0890.05002
  11. [11] A. Meir and J.W. Moon, Relations between packing and covering numbers of a tree, Pacific J. Math. 61 (1975) 225-233. Zbl0315.05102
  12. [12] J. Puech, Irredundant and independent perfect neighborhood sets in graphs, (preprint). Zbl0961.05053
  13. [13] J. Topp and L. Volkmann, On packing and covering numbers of graphs, Discrete Math. 96 (1991) 229-238, doi: 10.1016/0012-365X(91)90316-T. Zbl0759.05077

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.