DMS Combinatorics Seminar

Speaker: Arthur Tanyel (Auburn University)

Title: Degree sequence condition for Hamiltonicity in tough graphs

Abstract: Generalizing both Dirac's condition and Ore's condition for Hamilton cycles, Chvátal in 1972 established a degree sequence condition for the existence of a Hamilton cycle in a graph.  Hoàng in 1995 generalized Chvátal's degree sequence condition for 1-tough graphs and conjectured a \(t\)-tough analogue for any positive integer \(t\ge 1\). Hoàng in the same paper verified his conjecture for \(t\le 3\) and recently Hoàng and Robin verified the conjecture for \(t=4\). In this talk, we present a proof of the conjecture for all \(t\ge 4\). The proof depends on two newly established results on cycle structures in tough graphs, which hold independent interest.