Hamiltonian Decompositions of Complete Multipartite Graphs with Specified Leaves

Abstract

For any 2-regular spanning subgraph G and H of the complete multipartite graph K with p parts each of size m, conditions are found which guarantee the existence of a 2-factorization of K or of K - I (for some 1-factor I) in which 1. the first and second 2-factors are isomorphic to G and H respectively, and 2.each other 2-factor is a hamilton cycle These conditions are necessary and sufficient when m is odd, and solve the problem when m is even providing that m and p are each at least 6.