Hamilton cycles in highly connected and expanding graphs

Dan Hefetz, Michael Krivelevich, Tibor Szabo

Published 2006-12-24Version 1

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.