Studies On The Hamilton-Waterloo Problem

Combinatorial designs theory is an important branch of Discrete Mathematics,and the existence and construction of all kinds of designs is a basic problem in thetheory of Combinatorial designs. In 1847, Kirkman completely solved the problem forthe existence of a classic kind of designs, i.e. Steiner triple systems. From then on,designs have been developed quickly. In the last decades, more and more attentionhas been paid to the resolvable block designs. The well-known Kirkman's Schoolgirlsproblem asks for the existence of resolvable triple systems withλ= 1(Kirkman triplesystem), was solved separately by Ray-Chadhuri and Wilson[86], Jiaxi Lu[79].The problem for the existence of block designs is actually the problem for thedecomposition of graphs into complete graphs. For example, a Steiner triple system is adecomposition of a complete graph into complete graphs of order 3. After block designs,cycle decomposition problem naturally became an important problem of decompositionproblems. The problem can be tracked back to 1960s, Kotzig[67] and Rosa[90] determinedthe existence of k-cycle decompositions of the complete graph K2xk+1. After that,problems for cycle decompositions, especially resolvable cycle decompositions attractedmuch attention of experts and scholars. Hundreds of papers on this problem have beenpublished.The Oberwolfach problem is one of the most important problems for cycle de-compositions of complete graphs. It was first mentioned in 1967 by Ringle at a graphtheory meeting at the Oberwolfach conference center in Germany. The problem asksfor a decomposition of the complete graph into 2-factors(2-regular spanning subgraph),satisfy that all of the 2-factors are isomorphic to a given 2-factor F. When F is con-sisted of cycles of length 3, the problem is the Kirkman's schoolgirl problem. When F is a Hamilton cycle, the problem actually asks for a Hamilton cycle decomposition ofcomplete graphs.The Hamilton-Waterloo problem is a generalization of the Oberwolfach problem.For given 2-factors R and S, the problem asks for a decomposition of the complete graphKn (when n is odd) or Kn fi In(when n is even, In is a 1-factor) into 2-factors, and rof the 2-factors are isomorphic to R, s of the 2-factors are isomorphic to S. If R and Sare respectively consisted of cycles of length p and q, we call such a decomposition isuniformed, denote the 2-factorization by HW(n; r,s; p,q). In this paper, we deal withthe uniformed case of the Hamilton-Waterloo problem, especially when the 2-factorsare Hamilton cycles or consisted of cycles of length k(denoted by Ck-factor) for anygiven positive integer k.In chapter 1, we introduce the history of / progress on/ method for the Hamilton-Waterloo problem, and also the main results of this paper.In chapter 2, we give necessary conditions for the existence of HW(n; r,s; p,q) first.Then we deal with the problem for the existence of HW(n; r,s; n, 2k + 1) for both thecomplete graphs of even order and odd order. We prove that an HW(n; r,s; n, 2k + 1)exists when r is bigger than a number which is dependent on n and k.In chapter 3, we elaborate on the existence of HW(n; r,s; n, 3) when n is even.When n≡0 (mod 18), we prove that the necessary conditions given in chapter 2 arealso suficient with only 3 possible exceptions by using nearly Kirkman triple systems.When n≡6 (mod 18), we solve the problem except for the case r = 1 by usingKirkman 3-frames.In chapter 4, we deal with the problem for the existence of HW(n; r,s; n, 4k) forany given positive integer k. We prove that there exists an HW(n; r,s; n, 4k) if andonly if s = 0 or s=fi 0 and n≡0 (mod 4k) by using the results on cycle decompositionsof bipartite complete graphs.The last chapter is summary and concluding remarks.