Maximal sets of Hamilton cycles in complete multipartite graphs. IV (Q2142667)

Given a graph \(G\), a Hamilton cycle of \(G\) is a cycle containing every vertex of \(G\). If \(S\) is a set of edge-disjoint Hamilton cycles of \(G\), let \(E(S)\) be the set of edges that forms the cycles in \(S\). \(S\) is called maximal if \(G -E(S)\) contains no Hamilton cycles. Given \(K^p_n\), the complete \(p\)-partite graph with \(n\) vertices in each part, the authors in this paper deal with the problem of finding the integer \(\mu\) for which there exists a maximal set of \(\mu\) edge-disjoint Hamilton cycles in \(K^p_n\). The problem originated in a paper by \textit{D. G. Hoffman} et al. [J. Comb. Theory, Ser. B 57, No. 1, 69--76 (1993; Zbl 0767.05072)] and was later studied in other papers (see [\textit{D. E. Bryant} et al., J. Graph Theory 33, No. 1, 25--31 (2000; Zbl 0946.05052); \textit{M. Daven} et al., ibid. 43, No. 1, 49--66 (2003; Zbl 1028.05058); \textit{S. L. Jarrell} and \textit{C. A. Rodger}, Australas. J. Comb. 39, 207--217 (2007; Zbl 1141.05047); \textit{A. A. Noble} and \textit{C. A. Rodger}, J. Comb. Math. Comb. Comput. 82, 242--247 (2012; Zbl 1251.05093)], and the dissertation by \textit{A. A. Noble} [Maximal sets of Hamilton cycles in complete multipartite graphs. Auburn, AL: Auburn University (PhD Thesis) (2012)]). The culmination of these results combined with the results obtained in this paper by the authors is the complete spectrum of sizes for maximal sets of Hamilton cycles in \(K^p_n\). Theorem. There exists a maximal set of Hamilton cycles of size \(\mu\) of \(K^p_n\) if and only if \(\lceil n(p-1)/4\rceil \le \mu \le \lfloor n(p-1)/2\rfloor\) with the former inequality being strict when: \par 1.) \(n\) is odd and \(p\equiv 1 \pmod 4\) or \par 2.) \(p=2\).