Kt,n,n,n" <i>t< 2<i>n< i>}. <i>k<sub>n,n,n< surgical techniques, all members use two main methods build required results. first method cyclic generates entire embedding from sequence edge slopes satisfies certain conditions. lifting due bouchet his collaborators, 2. utilizes connection orthogonal latin squares exhibit structure. -- filling case prime <i>p< voltage ≠ 2.">

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 AbstractA central problem in topological graph theory is determining the (orientable or nonorientable) genus of a given graphG. For a general graphG, 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

F_{1}= {K+_{m}G|Gis ann-vertex graph andm≥n− 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 ofF_{1}, 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 ofF_{1}.The second family of graphs considered is the collection of complete quadripartite graphs

F_{2}= {K|_{t,n,n,n}t≥ 2n}. Using hamilton cycle embeddings ofKand some surgical techniques, we determine the orientable and nonorientable genus for all members of_{n,n,n}F_{2}.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

Kfor all_{n,n,n}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 casen= 2pfor a primepwith voltage graphs -- we obtain orientable hamilton cycle embeddings ofKfor all_{n,n,n}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.pdf642.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.