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.
References
[1]
Bermond, J.C. and Sch？nheim, J. (1977) G-Decomposition of Kn, Where G Has Four Vertices or Less. DiscreteMathematics, 19, 113-120. https://doi.org/10.1016/0012-365x(77)90027-9
[2]
Bermond, J.C., Huang, C., Rosa, A. and Sotteau, D. (1980) Decomposition of Complete Graphs into Isomorphic Subgraphs with Five Vertices. Ars Combinatoria, 10, 211-254. https://hal.science/hal-02333419
[3]
Doyen, J. and Wilson, R.M. (1973) Embeddings of Steiner Triple Systems. DiscreteMathematics, 5, 229-239. https://doi.org/10.1016/0012-365x(73)90139-8
[4]
Bryant, D.E., Rodger, C.A. and Spicer, E.R. (1997) Embeddings of M-Cycle Systems and Incomplete M-Cycle Systems: M ≤ 14. Discrete Mathematics, 171, 55-75. https://doi.org/10.1016/s0012-365x(96)00072-6
[5]
Hoffman, D.G. and Kirkpatrick, K.S. (2000) Another Doyen-Wilson Theorem. Ars Combinatoria, 54, 87-92. https://dblp.org/db/journals/arscom/arscom54.html
[6]
Hoffman, D.G., Lindner, C.C., Sharry, M.J. and Street, A.P. (1996) Maximum Packings of Kn with Copies of K4 ？ e. AequationesMathematicae, 51, 247-269. https://doi.org/10.1007/bf01833281
[7]
Back, R., Castano, A.B., Galindo, R. and Finocchiaro, J. (2021) A Decomposition of a Complete Graph with a Hole. OpenJournalofDiscreteMathematics, 11, 1-12. https://doi.org/10.4236/ojdm.2021.111001
[8]
Stern, G. and Lenz, H. (1980) Steiner Triple Systems with Given Subspaces: Another Proof of the Doyen-Wilson Theorem. Bollettino dell’Unione Matematica Italiana, 17, 109-114. https://www.scirp.org/reference/referencespapers?referenceid=2898387
