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.