Orientable hamilton cycle embeddings of complete tripartite graphs II: Voltage graph constructions and applications

Abstract

In an earlier article the authors constructed a hamilton cycle embedding of $K_{n,n,n}$ in a nonorientable surface for all $n\geq 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\ne 2$. In part II, a voltage graph construction is presented for building embeddings of the complete tripartite graph $K_{n,n,n}$ on an orientable surface such that the boundary of every face is a hamilton cycle. This construction works for all $n=2p$ such that $p$ is prime, completing the proof started by part I (which covers the case $n\ne 2p$) that there exists an orientable hamilton cycle embedding of $K_{n,n,n}$ for all $n\geq 1, n\ne 2$. These embeddings are then used to determine the genus of several families of graphs, notably $K_{t,n,n,n}$ for $t\geq 2n$ and, in some cases, $\overline{K_m}+K_n$ for $m\geq n-1$.