×

Multidesigns of the \(\lambda\)-fold complete graph for graph-pairs of orders 4 and 5. (English) Zbl 1067.05054

A graph-pair of order \(t\) consists of 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\). The only graph-pair of order \(4\) is \((C_4,K_2 + K_2)\), and there are a total of \(5\) graph-pairs of order \(5\). Given a graph-pair \((G, H)\), a partition of the edges of \(\lambda K_m\) into copies of \(G\) and \(H\) with at least one copy of \(G\) and at least one copy of \(H\) is called a \((G,H)\)-multidecomposition. When \(\lambda K_m\) does not admit a \((G,H)\)-multidecomposition, the problem is to find a maximum \((G,H)\)-multipacking (where the leave graph of remaining edges has as few edges as possible) and a minimum \((G,H)\)-multicovering (where the padding graph of excess edges has as few edges as possible). A multidesign is a multidecomposition, a maximum multipacking, or a minimum multicovering. The first two authors [Graphs Comb. 19, 433–447 (2003; Zbl 1032.05105)] completely determined the values of \(m\) for which \(K_m\) admits a \((G,H)\)-multidecomposition, when \((G,H)\) is a graph-pair of order \(4\) or \(5\). They also solved the corresponding maximum multipacking and minimum multicovering problems for graph-pairs of order \(4\) or \(5\). In this paper the authors solve the same problems for \(\lambda K_m\).

MSC:

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

Citations:

Zbl 1032.05105
PDFBibTeX XMLCite