The spectrum of path factorization of bipartite multigraphs  

作　　者：Jian WANG~1 Bei-liang DU~(2+) 1 Nantong Vocational College,Nantong 226007,China 2 Department of Mathematics,Suzhou University,Suzhou 215006,China 

出　　处：《Science China Mathematics》2007年第7期1045-1054,共10页中国科学：数学（英文版）

基　　金：This work was supported by the National Natural Science Foundation of China(Grant No.10571133).

摘　　要：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.LetλK_m,nbe a bipartite multigraph with two partite sets having m and n vertices, respectively.A P_v-factorization ofλK_m,nis a set of edge-disjoint P_v-factors ofλK_m,nwhich 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,nare（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.

关 键 词：bipartite multigraph FACTORIZATION 05B30 05C70 

分 类 号：O157.5[理学—数学]