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

Cited by in corpus (2)

• Sharp threshold for embedding combs and other spanning trees in random graphs
• Robust hamiltonicity of random directed graphs