dc.creator | Marshall, Emily Abernethy | |
dc.date.accessioned | 2020-08-21T21:19:22Z | |
dc.date.available | 2014-04-08 | |
dc.date.issued | 2014-04-08 | |
dc.identifier.uri | https://etd.library.vanderbilt.edu/etd-03212014-152116 | |
dc.identifier.uri | http://hdl.handle.net/1803/10999 | |
dc.description.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. | |
dc.format.mimetype | application/pdf | |
dc.subject | minor-free graphs | |
dc.subject | hamilton cycles | |
dc.subject | graph theory | |
dc.title | Hamiltonicity and Structure of Classes of Minor-Free Graphs | |
dc.type | dissertation | |
dc.contributor.committeeMember | Xiaoya Zha | |
dc.contributor.committeeMember | Denis Osin | |
dc.contributor.committeeMember | Michael Mihalik | |
dc.contributor.committeeMember | Jeremy Spinrad | |
dc.type.material | text | |
thesis.degree.name | PHD | |
thesis.degree.level | dissertation | |
thesis.degree.discipline | Mathematics | |
thesis.degree.grantor | Vanderbilt University | |
local.embargo.terms | 2014-04-08 | |
local.embargo.lift | 2014-04-08 | |
dc.contributor.committeeChair | Mark Ellingham | |