×

zbMATH — the first resource for mathematics

Hamilton decompositions of complete graphs with a 3-factor leave. (English) Zbl 1044.05058
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.

MSC:
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C45 Eulerian and Hamiltonian graphs
PDF BibTeX XML Cite
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.