Download PDF - An inequality chain of domination parameters for treesAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

An inequality chain of domination parameters for trees

Authors 1, 2, 2, 3

Affiliations

  1. Department of Mathematics, University of Victoria, Victoria, British Columbia, Canada V8W 3P4
  2. LRI, Bât. 490, Université de Paris-Sud, Orsay, France 91405
  3. Department of Mathematics, University of South Africa, PO Box 392, 0003 Pretoria, South Africa

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.

Keywords

ENG
domination, irredundance, packing, perfect neighbourhoods, annihilation

Bibliography

  1. E.J. Cockayne, O. Favaron, C.M. Mynhardt and J. Puech, A characterisation of (γ,i)-trees, (preprint).
  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).
  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).
  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.
  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).
  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).
  7. O. Favaron and J. Puech, Irredundant and perfect neighbourhood sets in graphs and claw-free graphs, Discrete Math. (to appear).
  8. G.H. Fricke, T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi and M.A. Henning, Perfect neighborhoods in graphs, (preprint).
  9. B.L. Hartnell, On maximal radius two independent sets, Congr. Numer. 48 (1985) 179-182.
  10. T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs (Marcel Dekker, 1997).
  11. A. Meir and J.W. Moon, Relations between packing and covering numbers of a tree, Pacific J. Math. 61 (1975) 225-233.
  12. J. Puech, Irredundant and independent perfect neighborhood sets in graphs, (preprint).
  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.
Discussiones Mathematicae Graph Theory
1998/18/1
Export to PBN, Opens in new tab
Pages:
127-142
Main language of publication
English
Received
1997-10-30
Published
1998

DOI: 10.7151/dmgt.1069

Exact and natural sciences