Hamilton cycles in highly connected and expanding graphs
Hamilton cycles in highly connected and expanding graphs
复制标题
高度连通和扩展图中的汉密尔顿循环
DOI：
10.1007/s00493-009-2362-0
复制
发表时间：
2006
期刊：
影响因子：
1.1
通讯作者：
Tibor Szabó
中科院分区：
文献类型：
--
作者：
Dan Hefetz;Michael Krivelevich;Tibor Szabó
在本文中，我们证明了存在汉密尔顿周期的足够条件，该循环适用于各种各样的图表，包括相对稀疏的图。小”集，另一个确保了任何两个不相交的“大”集合之间的边缘。
In this paper we prove a sufficient condition for the existence of a Hamilton cycle, which is applicable to a wide variety of graphs, including relatively sparse graphs. In contrast to previous criteria, ours is based on two properties only: one requiring expansion of “small” sets, the other ensuring the existence of an edge between any two disjoint “large” sets. We also discuss applications in positional games, random graphs and extremal graph theory.