Constructions of cubic bipartite 3-connected graphs with no Hamiltonian cycles

Alexander Kelmans

RUTCOR, Rutgers Univesity and University of Puerto Rico, San Juan

September 17,
3 pm (special time!)


Tutte conjectured that any cubic, bipartite, and 3-connected graph is Hamiltonian. It is also natural to consider Tutte's conjecture for cubic, bipartite, and cyclically 4-connected graphs.

We discribe different constructions of cubic, bipartite, and 3-connected graphs having no Hamiltonian cycle. Some of these constructions provide (infinitely many) graphs that are not only 3-connected but, moreover, cyclically 4-connected. The minimal such graph has 50 vertices and this graph is a minimal known counterexample to Tutte's conjecture. Moreover by means of these constructions we prove that if Barnette's conjecture (any cubic, bipartite, 3-connected and planar graph is Hamiltonian) is true, then a much stronger result is also true. No preparation is needed to understand this talk.

Speaker's Contact Info: kelmans(at-sign)

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)

Page loaded on September 04, 2003 at 02:16 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.