Fair Hamilton decompositions of complete multipartite graphs (Q1850614): Difference between revisions

A fair Hamilton decomposition of the complete multipartite graph \(G\) is a set of Hamilton cycles in \(G\) whose edges partition the edges of \(G\) in such a way that, for each pair of parts and for each pair of Hamiliton cycles \(H_1\) and \(H_2\), the difference in the number of edges in \(H_1\) and \(H_2\) joining vertices in these two parts is at most one. The authors prove the following theorem: There exists a fair Hamilton decomposition of \(K_{a_1,\ldots,a_p}\) if and only if \(a_1 = \cdots = a_p = m\) and \((p-1)m\) is even. The proof is constructive using graph homomorphisms which preserve the number of edges, but may identify adjacent vertices thereby generating (multiple) loops, which sometimes is called amalgamation.