The Properties Of Paths And Cycles With Different Conditions Of Degree In Two Kinds Of Graphs

The problem on paths and cycles of graphs is a very important problem in graph theory and the research is also active. Many practical problems can be at-tributed to the problem of paths and cycles. What is more, the famous Hamilton problem belongs to the problem of paths and cycles of graphs in essence. Many scholars at home and abroad made a lot of research work on this issue.The research results and progress in this area can be found in literature[34]-[38]. The condition of degree and neighborhood unions becomes an important way to study the problems. In this respect, a lot of outstanding achievements have be made. After the devel-opment for dozens of years, the contents in properties of graphs’ path and cycle become more and more rich and specific. The properties of path include Hamilton path (traceability), longest path, panconnectivity, path extendsibility and so on; the properties of cycle include Hamilton cycle, longest cycle,(vertex-)pancyclicity, vertex-disjoint cycle, cycle extendsibility and so on.However, we can not deny the fact that it is usually very difficult to study Hamilton problem in those graphs without any restriction. Then we turn to ex-plore the graphs not containing some forbidden subgraphs such as claw-free graphs. The first motivation for studying properties of claw-free graphs apparently appeared from Beineke’s characterization of line graphs in [18]. However, the main impulse that turned the attention of the graph theory community to the class of claw-free graphs was given in late 70s and early 80s. Some famous results about claw-free graphs can be seen in [1]-[3],[20]-[32]. In addition, the definition of claw-free graph has been extended to several larger graph families in different views, such as quasi-claw-free graphs, almost claw-free graphs, (K1,4; 2)- graphs etc.In this paper, we mainly discuss the relations between the degree condition (degree sums of three nonadjacent vertices, the sums of the order of neighborhood union and minimum degree) and properties of graphs’paths and cycles(including Hamil-ton connected, pancyclic,et.).And it gives some sufficient conditions of properties of graphs’ paths and cycles in claw-free graphs and quasi-claw-free graphs.In the first chapter, we give a brief introduction about the basic concepts, ter-minologies and symbols which will be used in this paper. In the meantime, we also give some related research backgrounds and some known results.In the second chapter, we mainly study the properties of paths and cycles with different conditions of degree in claw-free graphs and give the following results:Theorem 2.1 Let G be a 3- connected claw-free graph of order n, ifσ3(G)≥n+1, then G is pancyclic.Theorem 2.2 Let G be a 3- connected claw-free graph of order n, if NC(G)+δ(G)> n, then G is pancyclic.In the third chapter, we mainly study the properties of paths and cycles with different conditions of degree in quasi-claw-free graphs and give the following re-sults:Theorem 3.1 Let G be a 2- connected quasi-claw-free graph of order n. if NC(G)+δ(G)≥n-1, then G is Hamiltonian.Theorem 3.2 Let G be a 3- connected quasi-claw-free graph of order n≥3. if NC(G)+δ(G)≥n+1, then G is Hamilton connected.