Premium
Orientable Hamilton Cycle Embeddings of Complete Tripartite Graphs II: Voltage Graph Constructions and Applications
Author(s) -
Ellingham M. N.,
Schroeder Justin Z.
Publication year - 2014
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21783
Subject(s) - mathematics , combinatorics , embedding , graph , hamiltonian path , genus , surface (topology) , discrete mathematics , computer science , geometry , botany , artificial intelligence , biology
In an earlier article the authors constructed a hamilton cycle embedding of K n , n , nin a nonorientable surface for all n ≥ 1 and then used these embeddings to determine the genus of some large families of graphs. In this two‐part series, we extend those results to orientable surfaces for all n ≠ 2 . In part II, a voltage graph construction is presented for building embeddings of the complete tripartite graph K n , n , non an orientable surface such that the boundary of every face is a hamilton cycle. This construction works for all n = 2 p such that p is prime, completing the proof started by part I (which covers the case n ≠ 2 p ) that there exists an orientable hamilton cycle embedding of K n , n , nfor all n ≥ 1 , n ≠ 2 . These embeddings are then used to determine the genus of several families of graphs, notably K t , n , n , nfor t ≥ 2 n and, in some cases,K m ¯ + K nfor m ≥ n − 1 .