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

Title page for ETD etd-03202012-170814


Type of Document Dissertation
Author Schroeder, Justin Zane
Author's Email Address justin.z.schroeder@vanderbilt.edu
URN etd-03202012-170814
Title Hamilton cycle embeddings of complete tripartite graphs and their applications
Degree PhD
Department Mathematics
Advisory Committee
Advisor Name Title
Mark Ellingham Committee Chair
C. Bruce Hughes Committee Member
Jeremy Spinrad Committee Member
Michael Mihalik Committee Member
Paul Edelman Committee Member
Keywords
  • covering triangulation
  • graph genus
  • graph embedding
Date of Defense 2012-05-14
Availability unrestricted
Abstract
A central problem in topological graph theory is determining the (orientable or nonorientable) genus of a given graph G. For a general graph G, this problem is very difficult (in fact, it is NP-complete). Thus, it is desirable to have large families of graphs for which the genus is known. In this thesis, we use hamilton cycle embeddings of complete tripartite graphs to help determine the genera of two special families of graphs.

The first family of graphs -- and the original motivation for this problem -- is the collection of join graphs F1 = {Km+G | G is an n-vertex graph and mn − 1}. The nonorientable genus for this family of graphs has been completely determined by Ellingham and Stephens. In the orientable case, they were able to determine the genus for some infinite subfamilies of F1, but their results are not complete. In this thesis, we present a tripling construction for these embeddings that is an extension of a doubling construction employed by Ellingham and Stephens. Using this construction, together with hamilton cycle embeddings of complete tripartite graphs, we obtain the orientable genus for some additional infinite subfamilies of F1.

The second family of graphs considered is the collection of complete quadripartite graphs F2 = {Kt,n,n,n | t ≥ 2n}. Using hamilton cycle embeddings of Kn,n,n and some surgical techniques, we determine the orientable and nonorientable genus for all members of F2.

We use two main methods to build the hamilton cycle embeddings of complete tripartite graphs that are required to obtain these results. The first method is a cyclic construction that generates the entire embedding from a sequence of edge slopes that satisfies certain conditions. Using this construction and some lifting results due to Bouchet and his collaborators, we obtain nonorientable hamilton cycle embeddings of Kn,n,n for all n ≥ 2. The second method is a construction that utilizes a connection to orthogonal latin squares that exhibit some additional structure. Using this construction -- and filling in the case n = 2p for a prime p with voltage graphs -- we obtain orientable hamilton cycle embeddings of Kn,n,n for all n ≠ 2.

Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  JZSthesis.pdf 642.61 Kb 00:02:58 00:01:31 00:01:20 00:00:40 00:00:03

Browse All Available ETDs by ( Author | Department )

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