On Bipartite Factorization of Complete Bipartite Multigraphs

Abstract

Let $\lambda K_{m,n}$ be a complete bipartite multigraph with two partite sets having $m$ and $n$ vertices, respectively. A $K_{p,q}$-factorization of $\lambda K_{m,n}$ is a set of edge-disjoint $K_{p,q}$-factors of $\lambda K_{m,n}$ which is a partition of the set of edges of $\lambda K_{m,n}$. When $\lambda =1$, Martin, in paper [Complete bipartite factorisations by complete bipartite graphs, Discrete Math., $167/168(1997),461-480]$, gave simple necessary conditions for such a factorization to exist, and conjectured those conditions are always sufficient. In this paper, we will give similar necessary conditions for $\lambda K_{m,n}$ to have a $K_{p,q}$-factorization, and prove the necessary conditions are always sufficient in many cases.