Embedding spanning trees in random graphs
Preprint
Abstract
We prove that if T is a tree on n vertices wih maximum degree D and the edge probability p(n) satisfies: np>c*max{D*logn,n^{\epsilon}} for some constant \epsilon>0, then with high probability the random graph G(n,p) contains a copy of T. The obtained bound on the edge probability is shown to be essentially tight for D=n^{\Theta(1)}.Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Local resilience of almost spanning trees in random graphsRandom Structures & Algorithms, 2010
- Large Bounded Degree Trees in Expanding GraphsThe Electronic Journal of Combinatorics, 2010
- Factors in random graphsRandom Structures & Algorithms, 2008
- Embedding nearly-spanning bounded degree treesCombinatorica, 2007
- Spanning Trees in Dense GraphsCombinatorics, Probability and Computing, 2001
- Expanding graphs contain all small treesCombinatorica, 1987
- The longest path in a random graphCombinatorica, 1981