## DIMACS TR: 2000-22

## Asymptotically Optimal Tree--Pacings in Regular Graphs

### Authors: Alexander Kelmans, Dhruv Mubayi and Benny Sudakov

**
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 $\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