Research On Parameters And Structures Of Spanning Trees In A Graph

The property of a spanning tree in a graph has been a main research topic in structural graph theory.The origin and development of the problem are related to the hamiltonian problem,which is a classical problem in graph theory.It is generally known that there is a hamiltonian path in a graph G if and only if there is a spanning tree with at most 2 leaves in G.In this dissertation,we address the following more general question.For a given positive integer k? 2,what are the best possible sufficient conditions to guarantee the existence of a spanning tree with at most k leaves in a graph G?At present,the research on the existence of spanning trees satisfying certain conditions is mainly from the perspective of parameters such as toughness,inde-pendent number,connectivity,sum of degree,at domestic and overseas.This paper mainly studies the spanning tree in the forbidden subgraph and gives the sufficient condition for the existence of a spanning tree which satisfies a certain condition.This thesis is divided into five sections and the main content is as followsIn the first section,we give some definitions and notations which will be used in this paper.We then provide some background and previous results obtained by domestic and international researchers,state our results,and point out the signifi-cance of our results.This introduction will demonstrate that our work is necessary and new.Moreover,our results will have significant impact to the field.In the second section,we consider a sufficient condition for the existence of a spanning tree with at most 5 leaves in a connected K1,5-free graph.The problem proposed by Kyaw in[30].Kyaw proved the following result.Let G be a connected K1,4-free graph.The following conclusions hold.(1)If ?3(G)? |G|,then G has a hamiltonian path.(2)If ?k+1(G)? |G|-k/2 for an integer k>3,then G has a spanning tree with at most k leaves.A natural problem is for an integer k>4,whether there is a nonnegative function f(k)such that every connected K1,5-free graph G satisfying |G|=n and ?k+1l(G)?n-f(k)has a spanning tree with at most k leaves.Chen et.al considered the case of k= 4 and proved f(4)existed and the maximum value of f(4)was 1 in[12].In this section,we consider the case of k=5 and prove the following result.Let G be a connected K1,5-free graph.If?6(G)?|G|-1,then G contains a spanning tree with at most 5 leaves and the condition is sharp.Hence f(5)exists and the maximum value of f(5)is 1.The result is published in "Bulletin of the Malaysian Mathematical Science Society".In the third section,we consider a sufficient condition for the existence of a spanning tree with at most 5 leaves in a connected K1,5-free graph,that is,the case of k=6.The result is as follows.If ?7(G)? |G|-2,then G contains a spanning tree with at most 6 leaves and the condition is sharp.Hence f(6)exists and the maximum of f(6)is 2.The result is published in"Mathematical Problems in Engineering".In the forth section,we discuss the general case of the above problem.By introducing the concepts of leaf independent set,outer spider and the core to describe the structural characteristics of the minimal counterexample of this problem,it is proved that every connected K1,5-free graph G such that ?k+1(G)?|G|-[k-2/3]contains a spanning tree with at most k leaves,where k is an integer with k>4 and the lower bound of the result is also best possible.Therefore,f(k)exists and the maximum value is[k-2/3].In the fifth section,we give some problems which can be further considered and discussed.