Twofold $2$-Perfect $8$-Cycle Systems with an Extra Property

Abstract

A twofold 8-cycle system is an edge-disjoint decomposition of a twofold complete graph (which has two edges between every pair of vertices) into 8-cycles. The order of the complete graph is also called the order of the 8-cycle system. A twofold 2-perfect $8$-cycle system is a twofold $8$-cycle system such that the collection of distance $2$ edges in each $8$-cycle also cover the complete graph, forming a (twofold) $4$-cycle system. Existence of $2$-perfect $8$-cycle systems for all admissible orders was shown in [1], although $\lambda$-fold existence for $\lambda >1$ has not been done.

In this paper, we impose an extra condition on the twofold $2$-perfect $8$-cycle system. We require that the two paths of length two between each pair of vertices, say $x,a_{xy},y$ and $x,b_{xy},y$, should be distinct, that is, with $a_{xy}\ne b_{xy}$; thus they form a $4$-cycle $(x,a,y,b)$.

We completely solve the existence of such twofold $2$-perfect $8$-cycle systems with this “extra” property. All admissible orders congruent to $0$ or $1$ modulo $8$ can be achieved, apart from order 8.