Hamiltonian embeddings from triangulations

A Hamiltonian embedding of K n is an embedding of K n in a surface, which may be orientable or non‐orientable, in such a way that the boundary of each face is a Hamiltonian cycle. Ellingham and Stephens recently established the existence of such embeddings in non‐orientable surfaces for n = 4 and n ⩾ 6. Here we present an entirely new construction which produces Hamiltonian embeddings of K n from triangulations of K n when n ≡ 0 or 1 (mod 3). We then use this construction to obtain exponential lower bounds for the numbers of nonisomorphic Hamiltonian embeddings of K n .