Abstract
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 language | English |
|---|---|
| Pages (from-to) | 93-102 |
| Number of pages | 10 |
| Journal | Discrete Mathematics |
| Volume | 242 |
| Issue number | 1-3 |
| DOIs | |
| Publication status | Published - 1 Jun 2002 |
| Externally published | Yes |
Keywords
- Domination number
- Independent domination number
- Tree
- Tree-free domination number
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics