Genus embeddings of complete graphs minus a matching

Abstract

We show that for all $n\equiv 0(\mathrm{mod}6)$, $n\ge 18$, there is an orientable triangular embedding of the octahedral graph on $n$ vertices that can be augmented with handles to produce a genus embedding of the complete graph of the same order. For these values of $n$, the intermediate embeddings of the construction also determine some surface crossing numbers of the complete graph on $n$ vertices and the genus of all graphs on $n$ vertices and minimum degree $n-2$.

arXiv comment13 pages, 8 figures