A Fundamental Theorem of Multigraph Decomposition of a $\lambda K_{m,n}$

Abstract

Much research has been done on the edge decomposition of $\lambda$ copies of the complete graph $G$ with respect to some specified subgraph $H$ of $G$. This is equivalent to the investigation of $(G,H)$-designs of index $\lambda$. In this paper, we present a fundamental theorem on the decomposition of $\lambda$ copies of a complete bipartite graph. As an application of this result, we show that necessary conditions are sufficient for the decomposition of $\lambda$ copies of a complete bipartite graph into several multi-subgraphs $H$ with a number of vertices less than or equal to $4$ and the number of edges less than or equal to $4$, with some exceptions where decompositions do not exist. These decomposition problems are interesting to study as various decompositions do not exist even when necessary conditions are satisfied.