Almost 2-perfect 8-cycle systems

Abstract

For an $m$-cycle $C$, an inside $m$-cycle of $C$ is a cycle on the same vertex set, that is edge-disjoint from $C$. In an $m$-cycle system, $(\mathcal{X},\mathcal{C})$, if inside $m$-cycles can be chosen -one for each cycle- to form another $m$-cycle system, then $(\mathcal{X},\mathcal{C})$ is called an almost $2$-perfect $m$-cycle system. Almost $2$-perfect cycle systems can be considered as generalisations of $2$-perfect cycle systems. Cycle packings are generalisations of cycle systems that allow to have leaves after decomposition. In this paper, we prove that an almost $2$-perfect maximum packing of $K_n$ with $8$-cycles of order $n$ exists for each $n\ge 8$. We also construct a maximum $8$-cycle packing of order $n$ which is not almost $2$-perfect for each $n\ge 10$.