Packing k ‐edge trees in graphs of restricted vertex degrees

Let ${\cal G}^{s}_{r}$ denote the set of graphs with each vertex of degree at least r and at most s , v ( G ) the number of vertices, and τ k ( G ) the maximum number of disjoint k ‐edge trees in G . In this paper we show that (a1) if G ∈ ${\cal G}^{s}_{2}$ and s ≥ 4, then τ 2 ( G ) ≥ v ( G )/( s + 1), (a2) if G ∈ ${\cal G}^{3}_{2}$ and G has no 5‐vertex components, then τ 2 ( G ) ≥ v( G )4, (a3) if G ∈ ${\cal G}^{s}_{1}$ and G has no k ‐vertex component, where k ≥ 2 and s ≥ 3, then τ k ( G ) ≥ (v( G ) ‐ k )/( sk ‐ k + 1), and (a4) the above bounds are attained for infinitely many connected graphs.Our proofs provide polynomial time algorithms for finding the corresponding packings in a graph. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 306–324, 2007