Large Bounded Degree Trees in Expanding Graphs
Large Bounded Degree Trees in Expanding Graphs
复制标题
DOI：
10.37236/278
复制
发表时间：
2010-01
期刊：
影响因子：
--
通讯作者：
J. Balogh;Béla Csaba;M. Pei;Wojciech Samotij
中科院分区：
文献类型：
--
作者：
J. Balogh;Béla Csaba;M. Pei;Wojciech Samotij
Friedman和Pippenger的一个显著结果给出了一个图的扩张性质包含所有最大度有界的小树的充分条件。Haxell表明，在对扩张率稍微强一点的假设下，他们的技术允许人们找到具有有界最大度的任意大树。利用Haxell结果的一个较弱的版本，我们证明了一个扩展图族，其中包括非常稀疏的随机图和具有足够大的谱间隙的正则图，包含所有几乎生成有界度树.这改进了Alon，Krivelevich和Sudakov最近的两个树嵌入结果。
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.