Graphs and Matroids Seminar - Zishen Qu

Title: Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs

Abstract:

Finding sufficient conditions for a class of graphs to be Hamiltonian is an old problem, with a wide variety of conditions such as Dirac's degree condition and Whitney's theorem on 4-connected planar triangulations. We discuss some past results on sufficient conditions for Hamiltonicity involving the exclusion of fixed induced subgraphs, and some properties of the graphs involved in such results. In 1981 Duffus, Gould, and Jacobson showed that any connected graph that does not contain a claw or a net as an induced subgraph has a Hamiltonian path. We aim to find an analogous result for Hamiltonian cycles. In particular, we would like to find a set of graphs $S$ which are 2-connected, non-Hamiltonian, and every proper 2-connected induced subgraph is Hamiltonian such that every 2-connected $S$-free graph is Hamiltonian. In joint work with Joseph Cheriyan, Sepehr Hajebi, and Sophie Spirkl, we show that the classes of 2-connected split graphs and 2-connected triangle-free graphs can be characterised in this fashion.