上海交通大学 硕士学位论文 K=5时Hamilton-Waterloo问题的研究 姓名：赵鹏 申请学位级别：硕士 专业：数学 指导教师：沈灏 20090305 k = 5HamiltonWaterlooK Hamilton-WaterlooKKn2f)k r 2 f(2fQ?s2f,(2fR?P HW (n;r,s; Q,R).eKn2f)3K2fn1 2 l n 7 .w,2f7d|?Qdc1,c2, ,cq| Rdd1,d2, ,dt|PHW(n;c1,c2, ,cq;d1,d2, ,dt). ?QHamilton R3f(z2fd3| Pf)PHW(n;r,s;h,3)Horak169Dinitz17d/ .?QHamilton R4fP HW (n;r,s; h,4)23 . ?QHamilton R 5 fPHW(n;r,s;h,5)PHW(r,s;h,5)d Hamilton- Waterloo KPHW.-HW(n)LT/evkr8. HW(r,s;h,5)35K=HW(n). HW (n; r,s; h,5) n = h 1 (mod 2) n = h 0 (mod 5)l n = h 5 (mod 10). dK zK10k+52f)K= HW (10k + 5; r,s; h,5)35l HW(10k + 5). Kn2f)g,I?E2f x a?EHWIHamilton5f.|a?E HW(10k + 5;r,s;h,5)e(J 1 ?a K10k+5 ?k 0 (mod 2)HW(10k + 5) ?5 2k + 2, 5 2k + 3, , 5k + 2 ? HW(10k + 5). ?k 2 (mod 5)HW(10k + 5) 0,2,3,4 ,4k + 2,5k + 2 HW(10k + 5). 3:?k 2 (mod 10)HW(10k + 5) 0,2,3, ,50t + 12HW(10k + 5) t N50t + 12 10k + 5. ?k = 1 HW(15) HW(15) = 0,1,2,3,4,5,6,7. =uK10k+5?k 0 (mod 2)k 2 (mod 5)(l k 2 (mod 10) HW(10k + 5)k) d)?k = 1HW(15)k) ). c2f) x Hamilton5f -2- ?a Research on the Hamilton-Waterloo problem:The case of k = 5 Abstract The essential of the Hamilton-Waterloo problem is to research the 2 factorization of a complete graph Kn, in which r of the 2factors are isomorphic to a given 2factor Q and s of the 2factors are isomorphic to a given 2factor R, denoted HW(r,s;Q,R).It is easy to know that if there is a 2factorization of Kn, its number of 2factors is n1 2 , so n must be odd. It is obviously that the 2factors of a complete graph are consisted of cycles. We denote HW(n;c1,c2, ,cq;d1,d2, ,dt) when Q is consisted of cycles with c1,c2, ,cqlength, and R is consisted of cycles with d1, d2, ,dtlength. If Q is a complete graph s Hamilton cycle, and R is triangle factor(all the 2factors are consisted of cycles with 3 length, denoted factor), we denote it HW(n;r,s;h,3). Horak etc.16 and Dinitz17 have made the important research on this case. When Q is the complete graphs Hamilton cycle ,and R is 4 factor, we denote the problem HW(n;r,s;h,4). Luo Ming23 has done some research on this case. When Q is the complete graphs Hamilton cycle, and R is 5factor, we denote this case HW(n;r,s;h,5), or HW(r,s;h,5) abbreviatively. And we denote HWfor the Hamilton-Waterloo problem in this situation. Let HW(n) denotes the set of all the r which satisfi ed the conditions. This paper is to research the existence of the HW(r,s;h,5), namely to fi nd out the solution of HW(n). We can see that in the HW(n;r,s;h,5) n = h 1 (mod 2),and n = h 0 (mod 5),so n = h 5 (mod 10). Then the problem could be simplifi ed to research the 2 factorization of K10k+5.That is , to research the existence of HW(10k + 5;r,s;h,5), then to get the solution of HW(10k + 5). Obviously, to research the 2factorization of complete graph we need to construct the graphs 2factors. In this paper we use recursive diff erences method and mixed diff erence methodtwo important methodsto construct the Hamilton cycles and 5factors. By the strong construction tools, we get the following solutions -3- ?a of HW(10k + 5;r,s;h,5): For complete graph K10k+5,we give the partial solution of HW(10k + 5) when k 0 (mod 2): ?5 2k + 2, 5 2k + 3, , 5k + 2 ? HW(10k + 5). And we give the partial solution of HW(10k + 5) when k 2 (mod 5): 0,2,3,4 ,4k + 2,5k + 2 HW(10k + 5). Base of these we can get the partial solution of HW(10k + 5) when k 2 (mod 10): 0,2,3, ,50t + 12HW(10k + 5) t N50t + 12 10k + 5. When t = 1,we give all the solution of HW(15): HW(15) = 0,1,2,3,4,5,6,7. All of above, for the complete graph K10k+5, when k 0 (mod 2),k 2 (mod 5) (so that k 2 (mod 10),HW(10k + 5) has solutions, and we can give the partial of the solutions; When k = 1,HW(15) has solutions and we can get all of them. Key words: 2factorization, recursive diff erences, mixed diff erence, Hamilton cycle, 5-factors -4- ?a 1 1.10 Hamilton-WaterlooKCc5Jk|K KOberwolfachK.uOberwolfach Kk n Oberwolfach mIOt Sz Skai(1 i t) (u a1+ a2+ + at= nai 3)SzFY3n1 2 USz Tkk =kLg. OberwolfachK31967cdRingel3OberwolfachJl w:n Kn2f)K.KnL kn:Knf)fKnk fkK )f=Tfz:k.AKn 2 f 2K)f. OberwolfachKKn:?u?uX.duKnz2 fX uzdu?K S:= S .z8y.A Kn2f)