The triangle intersection problem for K4 - E designs

Abstract

An edge-disjoint decomposition of the complete graph Kn into copies of K4 - e, the simple graph with four vertices and five edges, is known to exist if and only if n ≡ 0 or 1 (mod 5) and n ≥ 6 (Bermond and Schönheim, Discrete Math. 19 (1997)). The intersection problem for K4 - e designs has also been solved (Billington, M. Gionfriddo and Lindner, J. Statist. Planning Inference 58 (1997)); this problem finds the number of common K4 - e blocks which two K4 - e designs on the same set may have. Here we answer the question: how many common triangles may two K4 - e designs on the same set have? Since it is possible for two K4 - e designs on the same set to have no common K4 - e blocks and yet some positive number of common triangles, this problem is largely independent of the earlier K4 - e intersection result.