The Possible Number of Cycles in Cycle Systems

Elizabeth J.Billington1, Darryn E.Bryant1
1Centre for Combinatorics Department of Mathematics The University of Queensland Brisbane Qld. 4072 AUSTRALIA

Abstract

For \(v \geq 3\), \(v\) odd, it is shown that there exists a decomposition of \(K_v\) into \(6\) cycles whose edges partition the edge set of \(K_v\), if and only if

\[\lfloor \frac{v-1}{2} \rfloor \leq b \lfloor \frac{v(v-1)}{6}\rfloor.\]
For even \(v\), \(v \geq 4\), a similar result is obtained for \(K_v\) minus a \(1\)-factor.