Asymptotically optimal tree-packings in regular graphs (Q5950387): Difference between revisions

Let \(T\) be a tree with \(t\) vertices. If \(G\) is a graph, then a \(T\)-packing of \(G\) is a subgraph of \(G\) each of whose connected components is isomorphic to \(T\). Clearly, if \(G\) has \(n\) vertices, then a \(T\)-packing of \(G\) contains at most \(n/t\) connected components. The authors prove the following asymptotic result for the maximum number of components in a \(T\)-packing. For every \(\varepsilon> 0\) there exists a real number \(D(\varepsilon, t)>0\) such that, if \(d> D(\varepsilon, t)\) and \(G\) is a simple \(d\)-regular graph on \(n\) vertices, then \(G\) contains at least \((1-\varepsilon)n/t\) vertex disjoint trees isomorphic to \(T\).