Research On Hamilton-Waterloo Problem

The 2-factorization of graphs is an important research object in graph theory and combinatorial design.Let Kv*be the complete graph Kv when v is odd or Kv minus a 1-factor I when v is even.Given two specified 2-factors F1 and F2,and two integers ? and ?,the Hamilton-Waterloo problem asks for a 2-factorization of Kv*into ? 2-factors isomorphic to F1 and all the other ? 2-factors isomorphic to F2.When F1 and F2 are uniform with cycle lengths m and n,we denote this problem to HWP(v;m,n;?,?).The research of HWP(v;m,n;?,?)originated in 1995.Since then it has attracted lots of attention from many scholars and many research results have been achieved.To find solutions of an HWP(v;m,n;?,?)has become a hot topic of graph theory and combinatorial design in recent years.We mainly use algebraic and combinatorial methods to study the existence of so-lutions of an HWP(v;m,n;?,?).Algebraic structures including difference matrices,Cayley graphs and so on are used for direct constructions.In particular,we gener-alize some ideas from cyclic difference sets and the mixed difference method posed by Bose,to construct solutions of HWP(v;m,n;?,?)s whose cycle sets can be par-titioned into several subsets with different automorphisms.Combinatorial methods are used for recursive constructions.By using combinatorial structures such as almost resolvable cycle systems,cycle frames and incomplete designs,we give a series of new recursive constructions for solutions of HWP(v;m,n;K?,?)s.The first major result of this thesis is about the existence of almost resolvable cycle system.A k-cycle system of order v whose cycle set can be partitioned into(v-1)/2 almost parallel classes and a half-parallel class is called an almost resolvable k-cycle system.We complete the proof of the existence of almost resolvable cycle system with odd cycle length.When the cycle length is even,we give a partial solution to an open problem posed by Lindner et al.on Combinatorica in 2010.The second main result is about the existence of solutions of the Hamilton-Waterloo problem,and the following results are obtained.We give a complete solution of HWP(v;3,n;?,?)for n?{4,5,7} and almost completely solve the existence of solutions of HWP(v;k,2kt+1;?,?)for odd k.Hence,we improve the known results of the Hamilton-Waterloo problem whose 2-factors have odd cycle length.We also almost completely solve the existence of solutions of HWP(8mt;8,m;?,?).