Spanning K-ended Tree And Path Cover Number Of Some Special Graphs

Graph theory is an interdisciplinary of computer science and mathematics,which is widely applied to biology,chemistry,medicine and other science,and application fields,such as,transportation,data networks.It is a classic structure problem to justify whether a graph is Hamilonian,that is,if there is a cycle which goes through all the vertices of the graph.The well-known Salesman problem is a Hamiltonian problem.As Hamiltonian problem is NP-hard,some special graphs are the key research objects;Moreover,there are a lot of related generalization problems,such as,the existence of some spanning trees,the minimum of path cover number and other problems of some special graphs.A spanning k-ended tree of a graph is a spanning tree with at most k leaves;Obviously,a spanning k-ended tree of a graph implies the possibility that if the graph contains a Hamiltonian cycle?or a Hamilton path?,that is,the less k is,the higher chance the graph contains a Hamiltonian cycle?or a Hamilton path?.A path cover of a graph is a spanning subgraph consisting of vertex-disjoint paths of the graph;A minimum path cover is a path cover containing the minimum number of paths,and the number of paths in a minimum path cover is called the path cover number.Likewise,the less path cover number of a graph is,the higher chance the graph contains a Hamiltonian cycle?or a Hamilton path?.Some results about the aforementioned contents will be presented in this thesis as follows:Win.et.al proved that if a graph contains a spanning k-ended system which is a spanning subgraph consisting of K₁,K₂,and some paths of length at least 3,then it contains a spanning k-ended tree.Based on the above result,in this thesis,we proposed a new spanning k-extended system consisting of K₁,K₂,some paths of length at least 3 and some special paths;Furthermore,if a graph contains a spanning k-extended system,then the graph contains a spanning k-ended tree.We proved that for an integer k?2 and a connected quasi-claw-free graph G,if the degree sum of any independent set consisting of k+1vertices is at least n-k,then G contains a spanning k-extended system,and then G contains a spanning k-ended tree.In this thesis,we proposed the definition of insertable vertex and non-insertable vertex of paths in a minimum path cover based on the definition of insertable vertex and non-insertable vertex of a longest cycle in a non-Hamiltonian graph proposed by C.Q.Zhang;Furthermore,we obtained the properties of the minimum path cover by the minimality of the minimum path cover.We mainly use the properties of the minimum path cover and the structure of K_1,4-free graphs to prove that if G is a K_1,4-free graph of order n such that the degree sum of any independent set consisting of k+1 vertices is at least n-k,then the path cover number is at most k;Furthermore,we mainly combined the properties of the minimum path cover with the structure of quasi-claw-free graphs to prove that if G is a quasi-claw-free graph of order n such that the degree sum of any independent set consisting of k+1 vertices is at least n-k,then the path cover number is at most k.