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\ge 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\ge 6$, that admit a $T$-multidecomposition. Moreover, we determine maximum multipackings and minimum multicoverings when $K_m$ does not admit a multidecomposition.