Type of Document Dissertation Author Marshall, Emily Abernethy Author's Email Address emily.a.marshall@vanderbilt.edu URN etd-03212014-152116 Title Hamiltonicity and Structure of Classes of Minor-Free Graphs Degree PhD Department Mathematics Advisory Committee

Advisor Name Title Mark Ellingham Committee Chair Denis Osin Committee Member Jeremy Spinrad Committee Member Michael Mihalik Committee Member Xiaoya Zha Committee Member Keywords

- minor-free graphs
- hamilton cycles
- graph theory
Date of Defense 2014-03-18 Availability unrestricted AbstractThe 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.

Files

Filename Size Approximate Download Time (Hours:Minutes:Seconds)

28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higher-speed Access Emily_Marshall_dissertation.pdf1.22 Mb 00:05:39 00:02:54 00:02:32 00:01:16 00:00:06

Browse All Available ETDs by
( Author |
Department )

If you have more questions or technical problems, please Contact LITS.