Trees with equal domination and tree-free domination numbers

Teresa W. Haynes, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


The tree-free domination number y(G; -Fk), k ≥ 2, of a graph G is the minimum cardinality of a dominating set S in G such that the subgraph (S) induced by S contains no tree on k vertices as a (not necessarily induced) subgraph (equivalently, each component of (S) has cardinality less than k). When k = 2, the tree-free domination number is the independent domination number. We obtain a characterization of trees with equal domination and tree-free domination numbers. This generalizes a result of Cockayne et al. (A characterisation of (y,i)-trees. J. Graph Theory 34(4) (2000) 277-292).

Original languageEnglish
Pages (from-to)93-102
Number of pages10
JournalDiscrete Mathematics
Issue number1-3
Publication statusPublished - 1 Jun 2002
Externally publishedYes


  • Domination number
  • Independent domination number
  • Tree
  • Tree-free domination number

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Trees with equal domination and tree-free domination numbers'. Together they form a unique fingerprint.

Cite this