2026/07/26 by Songling Shan, Arthur Tanyel
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph theory and applications #Matrix Theory and Algorithms
paper · pdf · doi:10.1002/jgt.70102
openalex created_date 2025/10/10 · openalex publication_date 2026/07/26 · openalex updated_date 2026/07/29
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 ‐tough analog for any positive integer . Hoàng in the same paper verified his conjecture for and recently Hoàng and Robin verified the conjecture for . In this paper, we confirm the conjecture for all . The proof depends on two newly established results on cycle structures in tough graphs, which hold independent interest.