Decompositions into 2-regular subgraphs and equitable partial cycle decompositions
The reviewer [Research problems, Problem 3, Discrete Math. 36, 333 (1981)] posed the following question in 1981. Given positive integers \(m_1,m_2,\dots,m_t\), all of which are at least 3 and at most \(n\), where \(n\) is odd, whose sum is \({{n}\choose{2}}\), is it possible to decompose the complete graph \(K_n\) into cycles of lengths \(m_1,m_2,\dots,m_t\)? The analogous problem for \(n\) even is that the sum should be \(n(n-2)/2\) and the target graph should be \(K_n\) with a 1-factor removed. We are a long way from a solution at this point in time. Outside of isolated special cases, not much is known. In a related direction, \textit{P. Balister} [Comb. Probab. Comput. 10, 463--499 (2001; Zbl 1113.05309)] proved the analogous result for even subgraphs (every vertex has even valency). The present paper takes Balister's result one step closer to the original problem. The authors prove that \(K_n\) and \(K_n-I\) can be decomposed into 2-factors with \(m_1,m_2,\dots, m_t\) edges, respectively. The authors also show that a partial cycle decomposition of \(K_n\) implies an equitable partial cycle decomposition with cycles of the same lengths.
scientific article; zbMATH DE number 2132708