Study On The Parameter And The Spanning Tree Of Graphs

The structure of graph is the core problem in graph theory.Spainning tree of graph is an important research topic in structural graph theory.The production and development of this problem are closely related to the famous Hamilton problem in the structure graph theory.It has extensive application in the fields of computer science,organic chemistry,power network analysis,shortest connection and channel design.It is widely concerned by graphic experts at home and abroad.The parameter of graph is the main tool of studying whether the graph exists Hamiltonian path(or cycle).The most common parameters are degree sum condition,independent number and so on.In this thesis,we studied spanning tree of graph.This dissertation consists of four sections.In Chapter 1,we introduce the research background and significance of spanning tree.In Chapter 2,we introduce graph-theoretical terminology and notation used in our discussion.In Chapter 3,we give some conditions for a connected graph to have a spanning tree possessing a certain prescribed property.A graph exists in Hamilton Road,which shows that there is a spanning tree with only two leaves or a maximum degree of 2 of the spanning tree.As the simplest type of tree,the road will naturally extend the following question: how to guarantee the existence of a spanning tree with a maximum degree at most k,or a spanning tree with at most k leaves in the graph.Recently,Rivera-Campo gave the degree sum condition of the spanning tree with simultaneous limits degree and number of leaves in the graph.Using the result of Kouider,we obtain the independent number condition of the spaning tree with the simultaneous limit degree and the number of leaves in the graph,which is the generalization of the results of Lara,Campo and Win.In 1998,Broersma and Tuinstra gave the degree sum condition of a spanning tree with at most k leaves in a graph.Under the same condition,we got a stronger result,and the spanning tree had a special structure.In particular,the spanning tree contain the longest path of the graph,especially in the larger order of the graph.As a weakening extension of the Hamilton circle,considering the cycle which contais given vertices in a graph is a recent research direction.We give a condition that a graph has an independent number condition with maximum degree at most k,which contains given vertices.Moreover,this condition is tight.Finally,we summarize the full text and look forward to the future research.