Multidesigns of Complete Graphs for Graph-Triples of Order 6

Charles A. Cusack1, Stephanie P. Edwards2, Darren B. Parker3
1Department of Computer Science, Hope College, Holland, MI 49423
2Department of Mathematics, Hope College, Holland, MI 49423
3Department of Mathematics, Grand Valley State University, Allendale, MI 49401- 6495

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.

Keywords: Multidecomposition, multidesign, multipacking, multicovering, graph decomposition.