Multidesigns of Complete Graphs for Graph-Triples of Order 6

Abstract

We call \( T = (G_1, G_2, G_3) \) a graph-triple of order \( t \) if the \( G_i \) are pairwise non-isomorphic graphs on \( t \) non-isolated vertices whose edges can be combined to form \( K_t \). If \( m \geq t \), we say \( T \) divides \( K_m \) if \( E(K_m) \) can be partitioned into copies of the graphs in \( T \) with each \( G_i \) used at least once, and we call such a partition a \( T \)-multidecomposition. For each graph-triple \( T \) of order \( 6 \) for which it was not previously known, we determine all \( K_m \), \( m \geq 6 \), that admit a \( T \)-multidecomposition. Moreover, we determine maximum multipackings and minimum multicoverings when \( K_m \) does not admit a multidecomposition.