Multidesigns for graph-pairs of order 4 and 5.(English)Zbl 1032.05105

Summary: The graph decomposition problem is well known. We say a subgraph $$G$$ divides $$K_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 order $$t$$, we mean two non-isomorphic graphs $$G$$ and $$H$$ on $$t$$ non-isolated vertices for which $$G\cup H\cong K_t$$ for some integer $$t\geq 4$$. 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 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 $$G\cup H\cong K_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.

MSC:

 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: