On Path Factorization Of Complete Multipartite Multigraphs

P_k^-factorization ofλG have been studied by many researchers and found a numberof applications.Especially,Yamamoto and Ushio etc [17] have given some applicationsin HUBMFS₂ schemes of database systems.There are also some known results onthe existence of the P_k^-factorization of complete multigraphsλK_m,complete bipartitemultigraphsλK_m,n and complete multipartite multigraphsλ(K_m*(?)_n).The existenceof P_k^-factorization ofλK_m have been completely solved by Horton [10] and Bermond,Heinrich and Yu [4].The existence of P_k^-factorization ofλK_m,n have been completelysolved by Ushio [12],Wang [14],Du [7] and Wang and Du [8,9,15,16].In this paper we will study P_k^-factorization ofλ(K_m*(?)_n).It is easy to seethatλ(K_m*(?)_n) has a P₂-factorization if and only if mn≡0 (mod 2).Ushio andTsuruno [13] and Du [6] have shown that the necessary conditions are also sufficient ifk = 3.Further,Yu [18] has shown that these two necessary conditions are sufficient ifk > 3 and k is a prime,and raise a conjecture:the necessary conditions for completemultipartite multigraphsλ(K_m * (?)_n) to have a P_k^-factorization are sufficent when pis not the power of prime.In our paper we will show that the necessary conditionsfor complete multipartite multigraphs to have a P_k^-factorization are sufficient whenk = p + 1 and p is prime.This answers the conjecture of Yu [18] on P_k^-factorizationsof complete multipartite multigraphs,when k = p + 1 and p is prime.