Maximal Sets of Hamilton Cycles in Complete Multipartite Graphs III

Abstract

A set of $S$ edge-disjoint Hamilton cycles in a graph $G$ is said to be $maximal$ if the Hamilton cycles in $S$ form a subgraph of $G$ such that $G–E(S)$ has no Hamilton cycle. The set of integers $m$ for which a graph $G$ contains a maximal set of $m$ edge-disjoint Hamilton cycles has previously been determined whenever $G$ is a complete graph, a complete bipartite graph, and in many cases when $G$ is a complete multipartite graph. In this paper, we solve half of the remaining open cases regarding complete multipartite graphs.