On complementary decompositions of the complete graph (Q1121285)

In this remarkable paper the authors consider decompositions \(K_ n\to H\), where H is either \(P_ 3\) (the path with 3 edges) or the complete bipartite graph \(K_{1,3}\), with the property that upon taking the complement of each graph in the decomposition one obtains a new decomposition \(K_ n\to H^ c.\) Two main results are obtained. The first is that a complementary decomposition \(K_ n\to P_ 3\) exists if and only if \(n\equiv 1\) modulo 3. The second result is that whenever \(n\equiv 1\) modulo 6 there exists a pair of complementary decompositions \(K_ n\to K_{1,3}\) and \(K_ n\to P_ 3\) (on the same \(K_ n)\) with the property that the graphs \(H_ 1,...,H_ t\) and \(J_ 1,...,J_ t\) corresponding to these decompositions satisfy \(H_ i\cup H^ c_ i=J_ i\cup J^ c_ i\) for \(i=1,...,t\) (that is, each decomposition gives rise to the same two- fold covering of \(K_ n\) by \(K_ 4s).\) More recent work involving subdesigns in such decompositions can be found in \textit{R. Rees} and \textit{D. R. Stinson}, On Combinatorial Designs with Subdesigns, Discrete Math. 77, 259-279 (1989), and in \textit{R. Rees} and \textit{C. A. Rodger}, Subdesigns in Complementary Path Decompositions and Incomplete Two-fold Designs with Block Size Four, to appear in Graphs and Combinatorics.