Events

DMS Combinatorics Seminar

Time: Apr 23, 2025 (02:00 PM)
Location: 328 Parker Hall

Details:

tanyel

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 t1. Hoàng confirmed his conjectures respectively  for t3 and t=1. We apply our t-closure lemma to confirm both conjectures for all t4.

Second, we present that all 71-tough (2P2P1)-free graphs of order at least three are Hamiltonian. This research is inspired by Chvátal's conjecture that there exists a constant t0 such that all t0-tough graphs of order at least three are Hamiltonian. This conjecture is still open, but work has been done to find such a t0 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 P5