The K_1,k～--factorization Of Complete Bipartite Graphs

Let Km,n be a complete bipartite graph with two partite sets having m and n vertices, respectively. ~Km,n is the disjoint union of ?~ graphs each isomorphic to Km,n. A KI,k-factorization of XKm,n is a set of edge-disjoint KI,k-factors of XKm,n which partition the set of edges of XKm,n. The KI,k-factorization of XKm,n can be applied to combinatorial multiplevalued index-file organization schemes of order two in database systems (see [7]). So the KI,k-factorization of XKm.n has been studied by several researchers. And there are some known results. When k=2, the spectrum problem for K1,2-factorization of complete bipartite graph Km,n has been completely solved by Ushio [6]. When k is a prime number p, the spectrum problem for K1,~-factorization of complete bipartite graph Km~n has been partially solved. In paper [10], Wang investigated K1,~-factorization of Km,n and gave a sufficient condition for such a factorization to exist, whenever p is a prime number. Later, there are many work to extend Wang抯 result to the case of k is a positive integer. In paper [3, 4], Du extended Wang抯 result to the case of k is a prime power pU In paper [5], for prime product pq, Du investigated Kl,N-factorization Of Km,n and gave a sufficient condition for such a factorization to exist, whenever p and q are prime numbers. In this paper, it is shown that the conclusion in [10] is true for any positive integer k. We will give a sufficient condition for the existence of the Kl,k-factorization Of Kmn, whenever k is a positive integer, is that (1) m ~kn, (2) n~km, (3) km-n~kn-m~O (mod (k2-1)) and (4) (km-n)(kn-m) ~0 (mod k(k-1)(k2-l)(m+n)). And we will also give a similar result for the existence of the ~ k-factorization of XKmn.