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

Title page for ETD etd-03202018-112132

Type of Document Dissertation
Author O'Connell, Kelly Mary
URN etd-03202018-112132
Title Characterisation and Hamiltonicity of K_{1,1,t}-minor-free Graphs: A Fan-based Approach
Degree PhD
Department Mathematics
Advisory Committee
Advisor Name Title
Mark Ellingham Committee Chair
Bruce Hughes Committee Member
Jeremy Spinrad Committee Member
Mike Mihalik Committee Member
Paul Edelman Committee Member
  • graph minors
  • hamiltonicity
Date of Defense 2018-03-16
Availability unrestricted
This dissertation presents some new results in certain areas of structural graph theory. In particular we are concerned with graph minors, and classes of graphs characterised in part by forbidding certain minors. There are many important results on classes of minor-free graphs, for example Wagner's Theorem, which states that a graph is planar if and only if it does not contain K_5 or K_{3,3} as a minor.

We work specifically with classes of graphs that do not have a complete multipartite graph K_{1,1,t} as a minor. We introduce a type of induced subgraph called a fan and show that several graph properties are preserved under operations with these fans, allowing us to inductively prove significant results for classes of 3-connected K_{1,1,t}-minor-free graphs.

Our first result is a complete structural characterisation of 3-connected K_{1,1,4}-minor-free graphs. We also prove counting results for these, and characterise those that are planar and those that are Hamiltonian.

Secondly, we prove a Hamiltonicity result for the class of 3-connected planar K_{1,1,5}-minor-free graphs. In particular, we prove that with one exception, every 3-connected planar K_{1,1,5}-minor-free graph is Hamiltonian. The exception is the well-known Herschel graph, a bipartite graph on eleven vertices.

  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  KellyOconnell.pdf 624.22 Kb 00:02:53 00:01:29 00:01:18 00:00:39 00:00:03

Browse All Available ETDs by ( Author | Department )

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