Leaves for packings with block size four

Abstract

We consider maximum packings of edge-disjoint $4$-cliques in the complete graph $K_n$. When $n\equiv 1$ or $4(\mathrm{mod}12)$, these are simply block designs. In other congruence classes, there are necessarily uncovered edges; we examine the possible `leave' graphs induced by those edges. We give particular emphasis to the case $n\equiv 0$ or $3(\mathrm{mod}12)$, when the leave is $2$-regular. Colbourn and Ling settled the case of Hamiltonian leaves in this case. We extend their construction and use several additional direct and recursive constructions to realize a variety of $2$-regular leaves. For various subsets $S\subseteq \{3,4,5,\dots \}$, we establish explicit lower bounds on $n$ to guarantee the existence of maximum packings with any possible leave whose cycle lengths belong to $S$.

19 pages plus supplementary file