{3,4,8}-cycles Decomposition The Complete Graph

Let Kv be a complete graph,F is the 1-factor of Kv(when v≡0(mod 2)),if exists mi≥3,i=1,2,...,t,in which the length of Ci equals mi,that satisfy the condition as follows:Kv(orKv-F)=C1+C2+…+Ct,we said Kv(orKv-F)can be decomposed by mi-cycles.Obviously,the necessary conditions of the decomposition of the complete graph are:(ⅰ)3≤mi≤v,i=1,2,...,t；(ⅱ)m1+m2+…+mt=v(v-1)／2(v≡1(mod 2))；m1+m2+…+mt=v(v-2)／2(v≡0(mod 2)). That these simple conditions are sufficient was conjectured by Alspach in 1981[1].Thus, this problem was called Alspach's conjecture.This is such great that it is very difficult to prove it completely.To date,only a few spacial cases have been solved:(1)v≤14；(2)m1=m2=…=mt；(3)mi∈A,i=1,2,...,t.A∈{{3,4,5),{3,4,6},{4,6,8},{4,10},{6,10},{8,10 },{3,v},{v-2,v-1,v}}U{{2k,2k+1}|k≥2}.This paper mainly proves that this conjecture is right when mi∈{3,4,8},by way of the synthetical application for the formers' proving methods.Because 3 is odd,but the odd-cycle in complete bipartite graph is not possible.We meet across some difficulties in the constructing process,so some techniques and methods are used here.The first part of chapter 2 in this paper,we prove the conjecture is true when v≡0(mod 2).At the first,some lemmas which will be used bellow are given in this part.Then we obtain the conclusion using the following method:if there exists the corresponding GDD,PBD,they can decompose the Kv-F into several subgraphs with little degrees,and these subgraphs can be decomposed through discussing the cases of the solution.However,not all cases could only be solved with GDD or PBD,when we should ask other GDD for the decomposition and discussion of Kv-F according to the practical situation.There are also some ones that don't have corresponding GDD,in this way,we must apply other methods to solve this problem.For examples the concrete construction of special cases. In the second part,the case of v≡1(mod 2) is proved. Here we firstly use the method in the proof of mi∈{4,6,8}, that is to say,construction the path-graphs and dismantle the graph and reorganize it. So, at the beginning of this art we give the important lemma that if the{3,4,8}-cycle decomposition of Kv-4 has been given, the number of C8 when z≥(v-1)/2 can be obtained.Lastly,the case of the number of C8 when z< (v-1)/2 is solve through the method of letting the Kv can be decomposed into the union of subgraphs. Above all, the cases when v= 1(mod 2) are both obtained.The contents of chapter 3 is to summarise the second chapter simply,then we obtain the important theorem:Theorem:When mi∈{3,4,8},the Alspach's conjecture is right(i.e. the{3,4,8}-cycle decomposition of Kv(orKv-F) always exists).