TY - JOUR
T1 - Hamilton cycles in highly connected and expanding graphs
AU - Hefetz, Dan
AU - Krivelevich, Michael
AU - Szabó, Tibor
N1 - Funding Information:
* This paper is a part of the author’s Ph.D. thesis written under the supervision of Prof. Michael Krivelevich. † Research supported in part by a USA–Israel BSF grant and a grant from the Israel Science Foundation.
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=77955999158&partnerID=8YFLogxK
U2 - 10.1007/s00493-009-2362-0
DO - 10.1007/s00493-009-2362-0
M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???
AN - SCOPUS:77955999158
SN - 0209-9683
VL - 29
SP - 547
EP - 568
JO - Combinatorica
JF - Combinatorica
IS - 5
ER -