Embedding nearly-spanning bounded degree trees
Preprint
Abstract
We derive a sufficient condition for a sparse graph G on n vertices to contain a copy of a tree T of maximum degree at most d on (1-\epsilon)n vertices, in terms of the expansion properties of G. As a result we show that for fixed d\geq 2 and 0<\epsilon<1, there exists a constant c=c(d,\epsilon) such that a random graph G(n,c/n) contains almost surely a copy of every tree T on (1-\epsilon)n vertices with maximum degree at most d. We also prove that if an (n,D,\lambda)-graph G (i.e., a D-regular graph on n vertices all of whose eigenvalues, except the first one, are at most \lambda in their absolute values) has large enough spectral gap D/\lambda as a function of d and \epsilon, then G has a copy of every tree T as above.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Sparse pseudo‐random graphs are HamiltonianJournal of Graph Theory, 2002
- On the second eigenvalue and random walks in randomd-regular graphsCombinatorica, 1991
- Universal Graphs for Bounded-Degree Trees and Planar GraphsSIAM Journal on Discrete Mathematics, 1989
- Expanding graphs contain all small treesCombinatorica, 1987
- On large matchings and cycles in sparse random graphsDiscrete Mathematics, 1986
- On Universal Graphs for Spanning TreesJournal of the London Mathematical Society, 1983
- Long paths in sparse random graphsCombinatorica, 1982
- The longest path in a random graphCombinatorica, 1981
- On graphs which contain all small treesJournal of Combinatorial Theory, Series B, 1978
- Hamiltonian circuits in random graphsDiscrete Mathematics, 1976