P_(4k-1)-factorization of complete bipartite graphs

摘要

Let K_(m,n) be a complete bipartite graph with two partite sets having m and n vertices, respectively. A P_v-factorization of K_(m,n) is a set of edge-disjoint P_v-factors of K_(m,n) which partition the set of edges of K_(m,n). When v is an even number, Wang and Ushio gave a necessary and sufficient condition for the existence of P_v-factorization of K_(m,n). When v is an odd number, Ushio in 1993 proposed a conjecture. However, up to now we only know that Ushio Conjecture is true for v = 3. In this paper we will show that Ushio Conjecture is true when v = 4k - 1. That is, we shall prove that a necessary and sufficient condition for the existence of a P_(4k-1)-factorization of K_(m,n) is (1) (2k - 1)m ≤ 2kn, (2) (2k - 1)n ≤ 2km, (3) m + n ≡ 0 (mod 4k - 1), (4) (4k - 1)mn/[2(2k - 1)(m + n)] is an integer.