Some Conditions for Hamiltonicity in Tough Graphs

Abstract

This dissertation has two focuses, both concerning Hamiltonicity conditions in tough graphs. First, for any integer $t \ge 4$, we present a $t$-closure lemma that generalizes a closure lemma of Bondy and Chv\'atal from 1976. In 1995, Ho\`ang generalized Chv\'atal's degree sequence condition for Hamiltonicity in 1-tough graphs and posed two $t$-tough analogues for any positive integer $t \ge 1$. Ho\`ang confirmed his conjectures respectively for $t \le 3$ and $t=1$. We apply our $t$-closure lemma to confirm the two conjectures for all $t \ge 4$.

Second, we present that all 11-tough $(2P_2 \cup P_1)$-free graphs of order at least three are Hamiltonian. This research is inspired by Chv\'atal's conjecture that there exists a constant $t_0$ such that all $t_0$-tough graphs of order at least three are Hamiltonian. This conjecture is still open, but work has been done to find such a $t_0$ for certain graph classes. With our result, the conjecture is confirmed for all $R$-free graphs where $R$ is any five-vertex linear forest excepting $P_5$.