TY - JOUR

T1 - Embedding nearly-spanning bounded degree trees

AU - Alon, Noga

AU - Krivelevich, Michael

AU - Sudakov, Benny

N1 - Funding Information:
* Research supported in part by a USA-Israeli BSF grant, by NSF grant CCR-0324906, by a Wolfensohn fund and by the State of New Jersey. † Research supported in part by USA-Israel BSF Grant 2002-133, and by grants 64/01 and 526/05 from the Israel Science Foundation. ‡ Research supported in part by NSF CAREER award DMS-0546523, NSF grant DMS-0355497, USA-Israeli BSF grant, and by an Alfred P. Sloan fellowship.

PY - 2007/11

Y1 - 2007/11

N2 - 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 - ε)n vertices, in terms of the expansion properties of G. As a result we show that for fixed d ≥ 2 and 0 < ε < 1, there exists a constant c = c(d, ε) such that a random graph G(n, c/n) contains almost surely a copy of every tree T on (1 - ε)n vertices with maximum degree at most d. We also prove that if an (n, D, λ)-graph G (i.e., a D-regular graph on n vertices all of whose eigenvalues, except the first one, are at most λ in their absolute values) has large enough spectral gap D/λ as a function of d and ε, then G has a copy of every tree T as above.

AB - 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 - ε)n vertices, in terms of the expansion properties of G. As a result we show that for fixed d ≥ 2 and 0 < ε < 1, there exists a constant c = c(d, ε) such that a random graph G(n, c/n) contains almost surely a copy of every tree T on (1 - ε)n vertices with maximum degree at most d. We also prove that if an (n, D, λ)-graph G (i.e., a D-regular graph on n vertices all of whose eigenvalues, except the first one, are at most λ in their absolute values) has large enough spectral gap D/λ as a function of d and ε, then G has a copy of every tree T as above.

UR - http://www.scopus.com/inward/record.url?scp=44649140055&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=44649140055&partnerID=8YFLogxK

U2 - 10.1007/s00493-007-2182-z

DO - 10.1007/s00493-007-2182-z

M3 - Article

AN - SCOPUS:44649140055

SN - 0209-9683

VL - 27

SP - 629

EP - 644

JO - Combinatorica

JF - Combinatorica

IS - 6

ER -