\input zb-basic
\input zb-ioport
\iteman{io-port 06279785}
\itemau{Ellingham, M.N.; Schroeder, Justin Z.}
\itemti{Orientable Hamilton cycle embeddings of complete tripartite graphs. I: Latin square constructions.}
\itemso{J. Comb. Des. 22, No. 2, 71-94 (2014).}
\itemab
The embedding of graphs on surfaces of distinct genera both minimum and maximum are interesting aspects in topological graph theory. The authors interestingly link Latin square construction and orientable Hamiltonian embeddings of complete tripartite graphs. In their earlier works of 2006, 2007, 2009, they constructed a Hamiltonian cycle of embeddings $K_{n,n,n}$ in a non-orientable surface for $n\geq1$. Further they used these embeddings to determine the genus of some large families of graphs. For furthering this work, instead of non-orientable surfaces for all $n\geq1$, they consider orientable surfaces for all $n\neq2$. First they reconnoiter a connection between orthogonal Latin squares and embeddings. A product construction is given for building pairs of orthogonal Latin squares such that one member of the pair has a certain Hamiltonian property. And then these Hamiltoninian squares are used for constructing embeddings of the complete tripartite graphs $K'_{n,n,n}$ as an orientable surface such that the boundary of every face is a Hamiltonian cycle. This construction holds for all $n\geq1$ such that $n\neq2$ and $n\neq2p$, where $p$ is prime. It is further established by the authors that the Latin square construction can be utilized for getting Hamiltonian cycle embedding of $K_{n,n,n}$ and it can also be used to obtain triangulations of $K_{n,n,n}$. Most interestingly the authors develop, for the construction of the desired Latin squares, a new method called the ``step product'' construction, which is a generalization of the known product constructions. Secondly, the case of $n=2p$, when $p$ is a prime, is also considered, and applying these embeddings they obtain some genus results as well. This completes the proof that an orientable Hamiltonian cycle embedding of $K_{n,n,n}$ exists for all $n\geq1$, $n\neq2$, and $n=2p$ for every prime $p$. Also the concept of triangulation is further extended. Finally, they conclude by establishing a theorem which states that if $n\geq1$ such that $n\neq2$, $n\neq2p$, where $p$ is a prime, then there exists a ce-Hamiltonian Latin square of order $n$ that admits a 1-partition, and as a corollary to this they establish that if $n\geq1$ such that $n\neq2$, $n\neq2p$, where $p$ is a prime, then there exists an orientable face 2-colorable Hamiltonian cycle embedding of $K_{n,n,n}$ in which every face is an ABC face.
\itemrv{Ratnakaram Nava Mohan (Hyderabad)}
\itemcc{}
\itemut{orthogonal Latin squares; complete tripartite graphs; graph embedding; Hamiltonian cycle; triangulation}
\itemli{doi:10.1002/jcd.21375}
\end