Large Bounded Degree Trees in Expanding Graphs
Open Access
- 5 January 2010
- journal article
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 17 (1) , R6
Abstract
A remarkable result of Friedman and Pippenger gives a sufficient condition on the expansion properties of a graph to contain all small trees with bounded maximum degree. Haxell showed that under slightly stronger assumptions on the expansion rate, their technique allows one to find arbitrarily large trees with bounded maximum degree. Using a slightly weaker version of Haxell's result we prove that a certain family of expanding graphs, which includes very sparse random graphs and regular graphs with large enough spectral gap, contains all almost spanning bounded degree trees. This improves two recent tree-embedding results of Alon, Krivelevich and Sudakov.Keywords
This publication has 5 references indexed in Scilit:
- Local resilience of almost spanning trees in random graphsRandom Structures & Algorithms, 2010
- Local resilience of graphsRandom Structures & Algorithms, 2008
- Embedding nearly-spanning bounded degree treesCombinatorica, 2007
- Expanding graphs contain all small treesCombinatorica, 1987
- Hamiltonian circuits in random graphsDiscrete Mathematics, 1976