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.


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