The Metamorphosis of $K_4\mathrm{\setminus }e$ Designs Into Maximum Packings of $K_n$ With $4$-Cycles

Abstract

Let $K_4\mathrm{\setminus }e=\dots$. If we remove the “diagonal” edge, the result is a $4$-cycle. Let $(X,B)$ be a $K_4\mathrm{\setminus }e$ design of order $n$; i.e., an edge-disjoint decomposition of $K_n$ into copies of $K_4\mathrm{\setminus }e$. Let $D(B)$ be the collection of “diagonals” removed from the graphs in $B$ and $C(B)$ the resulting collection of $4$-cycles. If $C_2(B)$ is a reassembly of these edges into $4$-cycles and $L$ is the collection of edges in $D(B)$ not used in a $4$-cycle of $C_2(B)$, then $(X,(C_1(B)\cup C_2(B)),L)$ is a packing of $K_n$ with $4$-cycles and is called a metamorphosis of $(X,B)$. We construct, for every $n=0$ or $1$ (mod $5$) $>6$, $n\ne 11$, a $K_4\mathrm{\setminus }e$ design of order $n$ having a metamorphosis into a maximum packing of $K_n$ with $4$-cycles. There exists a maximum packing of $K_n$ with $4$-cycles, but it cannot be obtained from a $K_4\mathrm{\setminus }e$ design.