Packing tree factors in random and pseudo-random graphs

作者：Bal Deepak^*; Krivelevich Michael; Frieze Alan; Loh Po Shen

来源：ELECTRONIC JOURNAL OF COMBINATORICS, 2014, 21(2): P2.8.

DOI：10.37236/3285

• Tree factors
• Packing
• Random graphs
• Pseudo-random graphs

For a fixed graph H with t vertices, an H-factor of a graph G with n vertices, where t divides n, is a collection of vertex disjoint (not necessarily induced) copies of H in G covering all vertices of G. We prove that for a fixed tree T on t vertices and epsilon %26gt; 0, the random graph G(n,p), with n a multiple of t, with high probability contains a family of edge-disjoint T-factors covering all but an epsilon-fraction of its edges, as long as epsilon(4)np %26gt;%26gt; log(2) n. Assuming stronger divisibility conditions, the edge probability can be taken down to p %26gt; C log n/n. A similar packing result is proved also for pseudo-random graphs, defined in terms of their degrees and co-degrees.

• 出版日期2014-4-16