***********************************
                * Princeton Discrete Math Seminar *
                ***********************************


Date: Thursday 27th February, 4:30 in Fine Hall 224.
 
Speaker: David P. Moulton, IDA--Center for Communications Research--Princeton

Title: Maximal non-Hamiltonian graphs

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.

                       -----------

Next week: June Huh

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)