Maximal non-Hamiltonian graphs

David Moulton , CCR, Princeton University
Fine Hall 224

One way to study Hamiltonicity of graphs is to consider (edge-)maximal non-Hamiltonian graphs. For instance, Ore's sufficient condition for a graph to be Hamiltonian can be rephrased as saying that in any maximal non-Hamiltonian graph of order n, there are two nonadjacent vertices whose degrees sum to less than n. In fact, the Bondy--Chvatal Theorem says that this property holds for every pair of nonadjacent vertices. It is easy to show that every maximal non-Hamiltonian graph of order at least 3 is spanned by a figure-eight graph (the union of two cycles sharing a point, where we allow each cycle to degenerate to an edge). I conjecture that every 2-connected maximal non-Hamiltonian graph is spanned by a theta graph (a subdivision of K_{1,1,2}) and have shown that this holds for all graphs of order at most 20. I'll sketch this, proving a number of properties of such graphs along the way.