Let $T$ be a tree with $t$ vertices. Clearly, an $n$ vertex graph contains at most $n/t$ vertex disjoint trees isomorphic to $T$. In this paper we show that for every $\ep>0$, there exists a $D(\ep,t)>0$ such t hat, if $d>D(\ep,t)$ and $G$ is a simple $d$-regular graph on $n$ vertices, then $G$ contains at least $(1-\ep)n/t$ vertex disjoint trees isomorphic to $T$.
Keywords: graph, hypergraphs, packing, trees, matchings
DIMACS Home Page