Decomposition Of 2l Regular Graphs With Given Girth Into P_l

Regular graph is the simple kind of graph,so the study of graph's properties is begin from regular graph.Regular graph have stronger symmetry and especial properties that other kinds of graph without.So the study of regular graph is always the hot issue of graph theory.The study of decomposition,coloring,connectivity and other problems of regular graph have made big progress.A Pi decomposition of G is a set of edge disjoin paths length l that cover the edge set of G.In this paper,there will be prove that every 10 regular graphs without two triangle have edge on common have a P5 decomposition at first.Then Giving the existence of P1 decomposition of 21 regulars with girth at least l-1 base on above conclusion at the end of this paper.In chapter one,There will introduce the background of the study of graph theory and research status of decomposing of regular graph and give ome basic definitions,notations and fundamental theory about graph and path decomposition of regular graph.In chapter two,we can get a 2-factor decomposition of 10 regular graphs without two triangle have edge on common use the Petersen's 2-Factorization Theorem at first,and then decompose 10 regular graphs without two triangle into a 6 regular subgraph and a 4 regular subgraph by recombine the 2-factors.Then we can prove that 6 regular graphs have P3 decomposition by reusing the Petersen's 2-Factorization Theorem,introducing the notation of intension T3,and applying the Extreme Value Theory.As the same 6 regular graphs,introduce the notation of extension T5,we get a extension T5 decomposition of 10 regular graphs without two triangle have edge on common,then we can prove 10 regular graphs without two triangle have edge on common exist P5 decomposition by making espe-cially construction method of euler direction of 4 regular subgraph and applying the Extreme Value Theory.In chapter three,based on the exist of P5 decomposition of 10 regular graphs without two triangle have edge on common,conclude and conjecture that girth at least l-1 is a sufficient condition of 21 regular graphs have Pi decomposition.By using mathematical in-duction,introducing the notation of extension Ti,and applying the Extreme Value Theory,we can prove that 21 regular graphs with girth at least l-1 exist PL decomposition.