A joint project of the Graduate School, Peabody College, and the Jean & Alexander Heard Library

Title page for ETD etd-03212014-152116


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
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.

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.pdf 1.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.