Hamiltonian decompositions of complete regular s-partite graphs (Q1076042): Difference between revisions

Generalizing a method of the first author [Hamiltonian decompositions of complete graphs, J. Comb. Theory, Ser. B 36, 125-134 (1984; Zbl 0542.05044)], the authors give a procedure by which Hamiltonian decompositions of the complete s-partite graph K(n,...,n) can be constructed whenever (s-1)n is even. The main effort is devoted to extending partial decompositions to Hamiltonian decompositions. Several theorems are presented, e.g.: If \(1\leq b\leq a\leq m\), then any proper edge-coloring of K(a,b) with m colors can be extended to a Hamiltonian decomposition of K(2m,2m).