Embedding Handcuffed Designs into a Maximum Packing of the Complete Graph with $4$-Cycles

Abstract

A packing of $K_n$ with copies of $C_4$ (the cycle of length $4$), is an ordered triple $(V,\mathcal{C},L)$, where $V$ is the vertex set of the complete graph $K_n$, $C$ is a collection of edge-disjoint copies of $C_4$, and $L$ is the set of edges not belonging to a block of $\mathcal{C}$. The number $n$ is called the order of the packing and the set of unused edges $L$ is called the leave. If $C$ is as large as possible, then $(V,\mathcal{C},L)$ is called a maximum packing MPC$(n,4,1)$. We say that an handcuffed design $H(v,k,1)$ $(W,P)$ is embedded into an MPC$(n,4,1)$ $(V,C,L)$ if $W\subseteq V$ and there is an injective mapping $f:\mathcal{P}\to \mathcal{C}$ such that $P$ is a subgraph of $f(P)$ for every $P\in \mathcal{P}$. Let $\mathcal{S}\mathcal{H}(n,4,k)$ denote the set of the integers $v$ such that there exists an MPC$(n,4,1)$ which embeds an $H(v,k,1)$. If $n\equiv 1(\mathrm{mod}8)$ then an MPC$(n,4,1)$ coincides with a $4$-cycle system of order $n$ and $\mathcal{S}\mathcal{H}(n,4,k)$ is found by Milici and Quattrocchi, Discrete Math., $174(1997)$.

The aim of the present paper is to determine $\mathcal{S}\mathcal{H}(n,4,k)$ for every integer $n\not\equiv 1(\mathrm{mod}8)$, $n\ge 4$.