Trees with equal domination and tree-free domination numbers

摘要

The tree-free domination number γ(G; -J_k), k ≥ 2, of a graph G is the minimum cardinality of a dominating set S in G such that the subgraph induced by S contains no tree on k vertices as a (not necessarily induced) subgraph (equivalently, each component of 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 (γ, i)-trees. J. Graph Theory 34(4) (2000) 277-292).