Embedding bounded degree spanning trees in random graphs

Abstract

We prove that if a tree $T$ has $n$ vertices and maximum degree at most $\Delta$, then a copy of $T$ can almost surely be found in the random graph $\mathcal{G}(n,\Delta {\log }^{5}n/n)$.

14 pages

References in corpus (1)

• Universality of random graphs and rainbow embedding

Cited by in corpus (9)

• Almost all Steiner triple systems have perfect matchings
• Almost all Steiner triple systems are almost resolvable
• Packing trees of unbounded degrees in random graphs
• Sharp threshold for embedding combs and other spanning trees in random graphs
• Finding any given 2-factor in sparse pseudorandom graphs efficiently
• Finding tight Hamilton cycles in random hypergraphs faster
• Robust hamiltonicity of random directed graphs
• $K_r$-Factors in Graphs with Low Independence Number
• Factors in randomly perturbed hypergraphs