On Kp, Q-factorizations Of Complete Bipartite Multigraphs

LetλK_m,n be a complete bipartite multigraph with two partite sets having m and n vertices, respectively. A K_p,q-factor inλK_m,n is a spanning subgraph ofλK_m,n, each component of which is a complete bipartite graph K_p,q. If the edges ofλK_m,n can be partioned into K_p,q-factors, then we sayλK_m,n has a K_p,q-factorization. The graphλK_m,n is called K_p,q-factorizable whenever it has a K_p,q-factorization. In paper [14] a K_p,q-factorization ofλK_m,n is defined as a resolvable (m, n,p + q,λ) K_p,q-design.The K_p,q-factorization of a complete bipartite multigraphλK_m,n has been studied by many researchers and found a number of application. Especially, Yamamoto and Ushio ect [18] have given some applications in HUBMFS2 schemes of database systems. Whenλ= 1, N. Martin, in paper [6], gave simple necessary conditions for such a factorization to exist, and conjectured those conditions are always sufficient. Martin conjecture, from then on, has drawn focus from many researchers. Martin conjecture has been proved in many cases. The balanced case (m = n) was proved in a series of papers [6, 7, 8, 9]. But for unbalance case (m≠n), the problem became complicated. The case for (p, q) = (p,p + 1) was solved in [11, 5]. Also Martin [11] showed that the conjecture is true when gcd(q - p, x + y) = 1. In this paper, we will give similar necessary conditions forλK_m,n to have a K_p,q-factorization, and prove the necessary conditions are always sufficient when gcd(q - p,x + y) = 1. Especially, forλK_m,n to have a K_1,q-factorization, we continue the study of the unbalanced case to show the necesarry conditions are sufficient whenever y is sufficiently large.