Minimum-Excess $\{K_3,K_4\}$-Coverings of $K_{17}$, $K_{18}$, and $K_{19}$

Abstract

We determine the minimum-excess coverings of $K_{17}$, $K_{18}$, and $K_{19}$ by 3-cliques and 4-cliques, minimizing first the number of repeated edge occurrences and then the number of blocks. The three secondary optima are \[ C^ξ(17,\{3,4\},2)=29,\qquad C^ξ(18,\{3,4\},2)=33,\qquad C^ξ(19,\{3,4\},2)=35. \] For $K_{18}$ and $K_{19}$ the minimum excess is zero, so the optimal covers are decompositions, with block vectors $15K_3+18K_4$ and $13K_3+22K_4$, respectively. Their lower bounds follow directly from the known values $g^{(4)}(18)=33$ and $g^{(4)}(19)=35$ for pairwise balanced designs with maximum block size four. For $K_{17}$ the minimum excess is two and every optimal cover has block vector $12K_3+17K_4$. At this optimum the excess multigraph may be $P_3$ or $2K_2$, but not a double edge; in fact a cover with double-edge excess requires at least $31$ blocks. The new nonexistence arguments for order $17$ combine local congruence conditions with finite structural reductions and exact completion checks. Explicit constructions and reproducibility material for these computer-assisted steps accompany the manuscript.