Online Talk: Zishen Qu

Tuesday, March 29, 3pm ET (8pm GMT, 8am Wed NZDT)
Zishen Qu, University of Waterloo
Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs

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.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.