Research On The Hamilton-Waterloo Problem: The Case Of K=5

The essential of the Hamilton-Waterloo problem is to research the 2–factorization of a complete graph Kn, in which r of the 2–factors are isomorphic to agiven 2–factor Q and s of the 2–factors are isomorphic to a given 2–factor R, denotedHW(r,s;Q,R).It is easy to know that if there is a 2–factorization of Kn, it's numberof 2–factors is n?2 1, so n must be odd. It is obviously that the 2–factors of a completegraph are consisted of cycles. We denote HW(n;c1,c2,···,cq;d1,d2,···,dt) when Qis consisted of cycles with c1,c2,···,cq length, and R is consisted of cycles with d1,d2,···,dt length. If Q is a complete graph's Hamilton cycle, and R is trianglefactor(all the 2–factors are consisted of cycles with 3 length, denoted ?– factor), wedenote it HW(n;r,s;h,3). Horak etc.[16] and Dinitz[17] have made the importantresearch on this case. When Q is the complete graph's Hamilton cycle ,and R is 4–factor, we denote the problem HW(n;r,s;h,4). Luo Ming[23] has done some researchon this case. When Q is the complete graph's Hamilton cycle, and R is 5–factor, wedenote this case HW(n;r,s;h,5), or HW(r,s;h,5) abbreviatively. And we denoteHW? for the Hamilton-Waterloo problem in this situation. Let HW?(n) denotes theset of all the r which satisfied the conditions. This paper is to research the existenceof the HW(r,s;h,5), namely to find out the solution of HW?(n). We can see that inthe 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 simplified to research the 2– factorization ofK10k+5.That is , to research the existence of HW(10k + 5;r,s;h,5), then to get thesolution of HW?(10k + 5).Obviously, to research the 2–factorization of complete graph we need toconstruct the graph's 2–factors. In this paper we use recursive di?erences methodand mixed di?erence method–two important methods–to construct the Hamiltoncycles and 5–factors. By the strong construction tools, we get the following solutions of HW(10k + 5;r,s;h,5):For complete graph K10k+5,we give the partial solution of HW?(10k + 5) whenk≡0 (mod 2):And we give the partial solution of HW?(10k + 5) when k≡2 (mod 5):Base of these we can get the partial solution of HW?(10k + 5) when k≡2 (mod 10):When t = 1,we give all the solution of HW?(15):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 ofthe solutions; When k = 1,HW?(15) has solutions and we can get all of them.