## DIMACS TR: 2000-44

## Packing Trees in Graphes

### Authors: Alexander Kelmans

**
ABSTRACT
**

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
$\tau _k (G)$ the maximum number of disjoint $k$--edge trees in $G$.
In this paper we show that

(a1) if $G \in {\cal G}^s_2 $ and $s \ge 4$ then $\tau _2 (G) \ge v(G)/(s+1)$,

(a2) if $G \in {\cal G}^3_2 $ and $G$ has no 5--vertex components then
$\tau _2 (G) \ge v(G)/4$,

(a3) if $G \in {\cal G}^s_1 $ and $G$ has no $k$--vertex component
where $k \ge 2$ and $s \ge 3$ then
$\tau _k(G) \ge (v(G) - k)/(sk - k +1)$, and

(a3) the above bounds are attained for infinitely many connected graphs.
Our proofs provide polynomial time algorithms for finding the corresponding
packings in a graph.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-44.ps.gz

DIMACS Home Page