Geodesic
Large bounded degree trees in expanding graphs
The electronic journal of combinatorics, Tome 17 (2010)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/278
Classification : 05C05, 05C35, 05C80, 05D40
Mots-clés : expansion properties, small trees, bounded maximum degree, sparse random graphs, spectral gap, spanning bounded degree trees 
@article{10_37236_278,
     author = {J\'ozsef Balogh and B\'ela Csaba and Martin Pei and Wojciech Samotij},
     title = {Large bounded degree trees in expanding graphs},
     journal = {The electronic journal of combinatorics},
     year = {2010},
     volume = {17},
     doi = {10.37236/278},
     zbl = {1184.05022},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/278/}
}
TY  - JOUR
AU  - József Balogh
AU  - Béla Csaba
AU  - Martin Pei
AU  - Wojciech Samotij
TI  - Large bounded degree trees in expanding graphs
JO  - The electronic journal of combinatorics
PY  - 2010
VL  - 17
UR  - http://geodesic.mathdoc.fr/articles/10.37236/278/
DO  - 10.37236/278
ID  - 10_37236_278
ER  - 
%0 Journal Article
%A József Balogh
%A Béla Csaba
%A Martin Pei
%A Wojciech Samotij
%T Large bounded degree trees in expanding graphs
%J The electronic journal of combinatorics
%D 2010
%V 17
%U http://geodesic.mathdoc.fr/articles/10.37236/278/
%R 10.37236/278
%F 10_37236_278
József Balogh; Béla Csaba; Martin Pei; Wojciech Samotij. Large bounded degree trees in expanding graphs. The electronic journal of combinatorics, Tome 17 (2010). doi: 10.37236/278

Cité par Sources :