zbMATH — the first resource for mathematics

Hamilton decompositions of complete multipartite graphs with any 2-factor leave. (English) Zbl 1031.05108
Summary: For \(m \geq 1\) and \(p \geq 2\), given a set of integers \(s_1,\dots ,s_q\) with \(s_j \geq p+1\) for \(1 \leq j \leq q\) and \(\Sigma_{j=1}^q s_j=mp\), necessary and sufficient conditions are found for the existence of a Hamilton decomposition of the complete \(p\)-partite graph \(K_{m,\dots ,m}-E(U)\), where \(U\) is a 2-factor of \(K_{m,\dots ,m}\) consisting of \(q\) cycles, the \(j\)th cycle having length \(s_j\). This result is then used to completely solve the problem when \(p = 3\), removing the condition that \(s_j \geq p+1\).

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C45 Eulerian and Hamiltonian graphs
Full Text: DOI
[1] Bermond, J Combin Th Ser B 46 pp 142– (1989)
[2] Ph.D. Dissertation, University of West Virginia, 1996
[3] Hilton, Discrete Math 58 pp 63– (1986)
[4] Laskar, Discrete Math 14 pp 146– (1976)
[5] Leach, J Combin Designs 9 pp 460– (2001)
[6] and Design Theory, CRC Press, Boca Raton, 1997.
[7] Récréations Mathématiques, 2 (1892) Gauthiers Villars, Paris.
[8] Stern, Boll Un Mat Ital 5 pp 109– (1980)
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.