Hamiltonicity and Structure of Classes of Minor-Free Graphs

Abstract

The main results of this dissertation are Hamiltonicity and structural results for graphs on surfaces and graphs with certain forbidden minors.

The first result is related to a conjecture due to Grunbaum and Nash-Williams which states that all 4-connected graphs on the torus are Hamiltonian. One approach to prove this conjecture is to extend the proof techniques of a result due to Thomas and Yu which says that every edge of a 4-connected projective-planar graph is on a Hamilton cycle. However the analogous result is not true for graphs on the torus. Thomassen provided examples of 4-connected toroidal graphs such that some edges of each graph are not contained in any Hamilton cycle. Our result shows that these examples are critical in a certain sense.

The second and third results concern minor-free graphs. Tutte proved that every 4-connected planar graph is Hamiltonian. Not all 3-connected planar graphs are Hamiltonian, however: the Herschel graph is one example. Our second result proves that all 3-connected, planar, K_{2,5}-minor-free graphs are Hamiltonian. We give examples to show that the K_{2,5}-minor-free condition cannot be weakened to K_{2,6}-minor-free. The final result is a complete characterization of all K_{2,4}-minor-free graphs. To prove both of these results we first provide a characterization of rooted-K_{2,2}-minor-free graphs. We also prove several useful results concerning Hamilton paths in rooted K_{2,2}-minor-free graphs.