DIMACS TR: 2000-22

Asymptotically Optimal Tree--Pacings in Regular Graphs

Authors: Alexander Kelmans, Dhruv Mubayi and Benny Sudakov


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

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-22.ps.gz
DIMACS Home Page