Leach, C. D.; Rodger, C. A. Hamilton decompositions of complete graphs with a 3-factor leave. (English) Zbl 1044.05058 Discrete Math. 279, No. 1-3, 337-344 (2004). Summary: We show that for any 2-factor \(U\) of \(K_n\) with \(n\) even, there exists a 3-factor \(T\) of \(K_n\) such that \(E(U) \subset E(T)\) so that \(K_n - E(T)\) admits a Hamilton decomposition. This is proved with the method of amalgamations (graph homomorphisms), using a new result that concerns graph decompositions that are fairly divided, but not necessarily regular. Cited in 8 Documents MSC: 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C45 Eulerian and Hamiltonian graphs Keywords:Hamilton cycles; Complete graph; Amalgamation; Graph homomorphism PDF BibTeX XML Cite \textit{C. D. Leach} and \textit{C. A. Rodger}, Discrete Math. 279, No. 1--3, 337--344 (2004; Zbl 1044.05058) Full Text: DOI References: [1] Bermond, J.; Favaron, O.; Maheo, M., Hamilton decomposition of Cayley graphs of degree 4, J. combin. theory ser. B, 46, 142-253, (1989) · Zbl 0618.05032 [2] H. Buchanan II, Graph factors and Hamiltonian decompositions, Ph.D. Dissertation, West Virginia University, 1997. [3] DeWerra, D., Equitable colorations of graphs, Rev. fran. inf. rech. oper., 5, 3-8, (1971) · Zbl 0239.05112 [4] Hilton, A.J.W., Hamilton decompositions of complete graphs, J. combin. theory (B), 36, 125-134, (1984) · Zbl 0542.05044 [5] Hilton, A.J.W.; Rodger, C.A., Hamilton decompositions of complete regular s-partite graphs, Discrete math., 58, 63-78, (1986) · Zbl 0593.05047 [6] Laskar, R.; Auerbach, B., On the decompositions of r-partite graphs into edge-disjoint Hamilton circuits, Discrete math., 14, 146-155, (1976) [7] Leach, C.D.; Rodger, C.A., Non-disconnecting disentanglements of amalgamated 2-factorizations of complete multipartite graphs, J. combin. des., 9, 460-467, (2001) · Zbl 0994.05125 [8] C.D. Leach, C.A. Rodger, Hamilton decompositions of complete multipartite graphs with any 2-factor leave, to appear. · Zbl 1031.05108 [9] D.E. Lucas, Recreations Mathématiques, Vol. 2, Gauthiers Villars, Paris, 1892. [10] McDiarmid, C.J.H., The solution of a timetabling problem, J. inst. math. appl., 9, 23-34, (1972) · Zbl 0243.90046 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.