Research On The Support Tree Problem Under The Condition Of Forbidden Subgraph

The spanning tree problem is a classical and important problem in graph theory,which is a general problem of Hamiltonian problem.In recent decades,many graph theory experts have devoted themselves to the study of spanning tree problem,and have obtained many meaningful results.And the related research on the spanning tree problem has helped people solve many real-life problems,such as the use of the minimum spanning tree to optimize the national grid.In this thesis,we mainly study the number of leaves of the spanning tree under the condition of forbidden subgraphs.The following two topics are specifically studied:(1)the number of leaves of the spanning tree in a connected K1,5-free graph under degree sum condition;(2)the number of leaves of the spanning tree in a connected K1,4-free graph under implicit degree sum conditions.We have constructed our work into four chapters.In Chapter 1,the background and research status of spanning tree under the condition of forbidden subgraph are introduced,and some related symbols and definitions are given.In Chapter 2,we study the spanning tree problem of K1,5-free graphs and prove that"if G is a connected K1,5-free graph,and the degree sum of any five nonadjacent vertices is at least |G|-1,then G contains a spanning tree with at most 4 leaves".Moreover,we give an example to show that the bound of this conclusion is sharp(the results were published on Discrete mathematics).In Chapter 3,we discuss the spanning tree problem of K1,4-free graphs.On the one hand,for a connected K1,4-free graph G,the implicit-degree sum condition is given to make the graph containing a Hamiltonian path.On the other hand,we consider the implicit-degree sum condition for a connected K1,4-f ree graph containing a spanning tree with at most 3 leaves.Moreover,we give examples to show that the bounds of these two conclusions are sharp.In chapter 4,we give a brief summary of the thesis,and the problems to be studied in the future.