TITLE:
K4 − e Designs on Complete Graphs with a Hole When 5 Divides the Order
AUTHORS:
Roxanne Back
KEYWORDS:
Graph Decomposition, Combinatorial Design, Complete Graph with a Hole, Difference Methods, 1-Factorization
JOURNAL NAME:
Open Journal of Discrete Mathematics,
Vol.16 No.4,
September
2,
2026
ABSTRACT: In a companion paper, we settled the existence of K4 − e designs on Kd + v for even d with v = 2(d − 1) − 5a, treating the cases where a is even and odd separately. In this paper, we complete the full characterization for even d by resolving the remaining case: 5 | d. We first establish non-existence when v = 2d − 3 or v = 2d − 4 via a coloring argument. We then prove existence for all admissible v using a combination of direct constructions, a multipartite design on K10,10,10, and a recursive blowup lemma. Together with our earlier results, this yields a complete necessary and sufficient characterization: a K4 − e design on Kd + v exists when d is even if and only if 5 | d(d + 2v − 1), v ≤ 2(d − 1), and v ≠ 2d − 3, v ≠ 2d − 4.