Multidesigns for graph-pairs of order 4 and 5

The graph decomposition problem is well known. We say a subgraph GdividesK(m) if the edges of K-m can be partitioned into copies of G. Such a partition is called a G-decomposition or G-design. The graph multidecomposition problem is a variation of the above. By a graph-pair of ordert, we mean two non-isomorphic graphs G and H on t non-isolated vertices for which Gboolean ORHcongruent toK(t) for some integer tgreater than or equal to4. Given a graph-pair (G,H), if the edges of K-m can be partitioned into copies of G and H with at least one copy of G and one copy of H, we say (G,H) divides K-m. We will refer to this partition as a (G,H)-multidecomposition. In this paper, we consider the existence of multidecompositions for several graph-pairs. For the pairs (G,H) which satisfy Gboolean ORHcongruent toK(4) or K-5, we completely determine the values of m for which K-m admits a (G,H)-multidecomposition. When K-m does not admit a (G,H)-multidecomposition, we instead find a maximum multipacking and a minimum multicovering. A multidesign is a multidecomposition, a maximum multipacking, or a minimum multicovering.