Hamilton cycles in highly connected and expanding graphs

• DOI: 10.1007/s00493-009-2362-0
• Publication Date: 2010-08-23T00:12:01Z
• Authors: Dan Hefetz; Michael Krivelevich; Tibor Szabó
• Keywords: Disjoint sets; Cograph; Indifference graph

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 only two properties: 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.<br/>19 pages<br/>