The spectrum of path factorization of bipartite multigraphs

LetλK_(m,n)be a bipartite multigraph 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,Ushio,Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a P_v-factorization ofλK_(m,n).When v is an odd number,we have proposed a conjecture.Very recently,we have proved that the conjecture is true when v=4k-1.In this paper we shall show that the conjecture is true when v = 4k 1,and then the conjecture is true.That is,we will prove that the necessary and sufficient conditions for the existence of a P_(4k 1)-factorization ofλK_(m,n)are(1)2km≤(2k 1)n,(2)2kn≤(2k 1)m,(3)m n≡0(mod 4k 1),(4)λ(4k 1)mn/4k(m n)]is an integer.

The spectrum of path factorization of bipartite multigraphs

Let λK _m,n be a bipartite multigraph 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, Ushio, Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a P _v-factorization of λK _m,n . When v is an odd number, we have proposed a conjecture. Very recently, we have proved that the conjecture is true when v = 4k − 1. In this paper we shall show that the conjecture is true when v = 4k + 1, and then the conjecture is true. That is, we will prove that the necessary and sufficient conditions for the existence of a P _4k+1-factorization of λK _m,n are (1) 2km ⩽ (2k + 1)n, (2) 2kn ⩽ (2k + 1)m, (3) m + n ≡ 0 (mod 4k + 1), (4) λ(4k + 1)mn/4k(m + n)] is an integer. This work was supported by the National Natural Science Foundation of China (Grant No. 10571133).