| The edge decomposition problem of a graph G is a classical problem in graph theory,which is widely used in coloring and partition problems of graph.The edge decomposition problem of cubic graphs can be traced back to Vizing edge colouring theorem.It shows that every cubic graph can be decomposed into four edge-disjoint matchings.In 2011,Hoffmann-Ostenhof put forward the following Conjecture:every connected cubic graph G has an edge decomposition {T,M,C} such that T is a spanning tree,M is a matching and C is a set of disjoint cycles.In this thesis,we will consider the Hoffmann-Ostenhof’s Conjecture and some related problems for cubic graphs with some forbidden structure.The thesis is organized as follows:In Chapter 1,we give some basic terminologies and notations used in this thesis.Then,we introduce the history of edge decomposition problem,and some proved results about Hoffmann-Ostenhof’s Conjecture.Finally,we list the main results of this thesis.In Chapter 2,we shall prove the conjecture holds for connected claw-free graphs.In fact,we will give a stronger result by restrict an edge appears only on the tree or on the matching in the decomposition,and prove that if G is a connected claw-free cubic graph and e is an edge of G that is not contained in any triangles,then G can be decomposed into a spanning tree T,a matching M and a family of cycles C,such that e E E(T)U E(M).In Chapter 3,we consider the connected graph with maximum degree at most 3,and proved that G can be decomposed into a spanning tree and a matching,if G is a connected graph with the maximum degree at most 3 such that every vertex with degree three in G has a neighbor with degree two.The result gives a partial answer of the problem Hoffmann-Ostenhof raised about connected graphs with maximum degree at most 3.On this basis,we can proved that Hoffmann-Ostenhof’s Conjecture holds for connected double-claw-free cubic graphs.In Chapter 4,we give some further research about Hoffmann-Ostenhof’s Conjecture. |
PDF Full Text Request