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 graph theory for decades. The origin and development of the problem, which have attracted the scholars’attention all over the world, are closely related to hamiltonian problem in structural graph theory. There exists a hamiltonian path in a graph, that is to say that the graph has a spanning tree with exactly2leaves, or maximum degree2, or no branch vertex. Naturally, there are many problems worth reflecting. Which conditions can guarantee the existence of a spanning tree with some special properties such as at most k leaves,or bounded branch vertices, or maximum degree at most k and so on in a graph? Meanwhile, if a graph G is a hamiltonian connected graph, that is to say that there exists a spanning tree with any pair of vertices as its leaves. Then we can try to find that which conditions can guarantee the existence of a spanning tree with any k vertices as its leaves in a graph, leading to the determining problem of k-leaf connected graph.It is well-known that the problem of determining problem whether a given graph has a hamiltonian path or not is N P-complete. We know that the above mentioned series of problems of determining a graph to have a spanning tree with corresponding properties or not are also N P-complete. Hence the scholars mainly deal with sufficient conditions for a graph to have such a spanning tree.In the current study of the spanning tree possessing the properties concerning hamiltonian properties, the research mainly utilize toughness, independence number, connectivity, neighborhood union, degree sum conditions and so on to give the sufficient conditions for a graph to have the following five types of spanning trees in terms of the parameter:1. spanning tree with maximum degree at most k;2.spanning tree with at most k branch vertices;3.spanning tree with at most k leaves in a graph of given connectivity, especially in K1,r-free graphs;4spanning tree with any k vertices as its leaves;5.spanning tree satisfying that maximum degree is at most k after deleting all the leaves.The thesis mainly gives some degree sum conditions to deal with the problems of the existence of spanning trees with bounded leaves in K1,4-free and K1,5-free graphs of given connectivity. Firstly, we consider the connected K1,4-free graph. Kyaw gave the following result. Let G be a connected K1,4-free graph of order n,(ⅰ)if σ3(G)≥n, then G has a hamiltonian path or a spanning tree with exactly2leaves.(ⅱ)if σk+1(G)≥n-k/2for k≥3,then G has a spanning tree with at most k leaves. He also showed that the above bounds are the best possible. In this thesis, we consider the graph with higher connectivity and obtain the following result. Let G be a m-connected K1,4-free graph of order n and m>2, if σm+3(G)≥n+2m-2, then G has a spanning tree with at most3leaves.Secondly, we also consider the similar problem in connected K1,5-free graph and obtain the following result. Let G be a connected K1,5-free graph of order n with n≥77, if σ5(G)≥n-1, then G has a spanning tree with at most4leaves.We also show that the degree sum bound of n-1is the best possible.