Events
DMS Combinatorics Seminar |
Time: Apr 23, 2025 (02:00 PM) |
Location: 328 Parker Hall |
Details: Speaker: Arthur Tanyel (Auburn University) Title: Some Conditions for Hamiltonicity in Tough Graphs
Abstract: This talk has two focuses, both concerning Hamiltonicity conditions in tough graphs. First, we present a \(t\)-closure lemma that generalizes a closure lemma of Bondy and Chvátal from 1976. In 1995, Hoàng generalized Chvátal's degree sequence condition for Hamiltonicity in 1-tough graphs and posed two \(t\)-tough analogues for any positive integer \(t \ge 1\). Hoàng confirmed his conjectures respectively for \(t \le 3\) and \(t=1\). We apply our \(t\)-closure lemma to confirm both conjectures for all \(t \ge 4\). Second, we present that all 71-tough \((2P_2 \cup P_1)\)-free graphs of order at least three are Hamiltonian. This research is inspired by Chvátal'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 \(F\)-free graphs where \(F\) is any five-vertex linear forest excepting \(P_5\). |