Events
DMS Combinatorics Seminar |
| Time: Apr 01, 2026 (01: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, for any integer \(t \ge 4\), 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 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á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 \(R\)-free graphs where \(R\) is any five-vertex linear forest excepting \(P_5\).
|
