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 hamilton cycles H-1 and H-2, the difference in the number of edges in H, and H2 joining vertices in these two parts is at most one. In this paper we completely settle the existence of such decompositions. The proof is constructive. using the method of amalgamations (graph homomorphisms). (C) 2002 Elsevier Science (USA). [References: 12]
展开▼
