Research On The Spanning Tree Problem Under The Condition Of Disabling Induced Subgraph

The spanning tree problem is an important and significant problem in structural graph theory.This problem is closely related to Hamiltonian problem.In recent years,many scholars have carried out continuous research on spanning tree problem,applied it to practice,and solved many problems in life.In this thesis,we mainly study the number of leaves and branch vertices of spanning trees under conditions of forbidden subgraphs.The following three topics are specifically studied:(1)the number of branch vertices of spanning trees in connected K1,4-free graphs under degree sum condition;(2)the tobal number of leaves and branch vertices of spanning trees in 2-connected graphs under the condition of maximum degree of the special vertex set;(3)the tobal number of leaves and branch vertices of spanning trees in connected K1,5-free graphs under degree sum condition.We have constructed our work into four chapters.In Chapter 1,we introduce the background,significance and development status of the spanning tree problem of graphs at home and abroad,and give the basic definitions and symbols that appear in the paper.In Chapter 2,we study the spanning tree problem of K1,4-free graphs and prove that"if G is a connected K1,4-free graph,and the degree sum of any k+3 nonadjacent vertices is at least |V(G)|-k,then G contains a spanning tree with at most k branch vertices".Moreover,we give an example to show that the bound of this conclusion is sharp.In Chapter 3,firstly,we discuss the spanning tree problem of 2-connected graphs and prove that "Let k≥3 be an integer and let G be a 2-connected graph.If max{dG(x),dG(y)}≥|V(G)|-k+1/2 for every two vertices x,y of every induced K1,3 or K1,3+e in G with distG(x,y)=2,then G contains a spanning tree with at most k+1 leaves and branch vertices".Secondly,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 four nonadjacent vertices is at least |V(G)|-1,then G contains a spanning tree with at most 5 leaves and branch vertices".In Chapter 4,the thesis is summarized briefly,and the future research of graph spanning tree is prospected.