Asymptotically Optimal Tree-Packings in Regular Graphs

Abstract

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 $\epsilon >0$, there exists a $D(\epsilon,t)>0$ such that, if $d>D(\epsilon,t)$ and $G$ is a simple $d$-regular graph on $n$ vertices, then $G$ contains at least $(1-\epsilon)n/t$ vertex disjoint trees isomorphic to $T$.