Embedding Spanning Trees in Random Graphs
Author:
- Michael KrivelevichMKMichael Krivelevich
- 1 January 2010
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 24 (4) , 1495-1500
Abstract
We prove that if T is a tree on n vertices with maximum degree $\Delta$ and the edge probability $p(n)$ satisfies $np\geq C\max\{\Delta\log n,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 $\Delta=n^{\Theta(1)}$.
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- 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
- Tree embeddingsJournal of Graph Theory, 2001
- Trees in sparse random graphsJournal of Combinatorial Theory, Series B, 1988
- Expanding graphs contain all small treesCombinatorica, 1987
- Limit distribution for the existence of hamiltonian cycles in a random graphDiscrete Mathematics, 1983
- The longest path in a random graphCombinatorica, 1981