Paths And Cycles Of Two Classes 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 attributed 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[40]-[43].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 development 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 explore 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 [16]-[17]. 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 [2]-[4], [18]-[34]. 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, (K_1,4;2)-graphs, DCT graphs etc. A.Ainouche[35] defined a new graph family -quasi-claw-free graphs and he also gave several results about paths and cycles in the new graph family.After that,many researchers have done a lot of work to study Hamilton problem in quasi-claw-free graphs[36]-[38]. In 2003,Teng Yanyan,You Haiyan,Lin Houyuan gave the defination of K_1,4-confined graphs(the latter named (K_1,4;2)-graphs)which contain the family of claw-free graphs.Many good results of claw-free graphs have been extended to (K_1,4; 2)-graphs.In this paper,we mainly study the paths and cycles of quasi-claw-free graphs and (K_1,4;2)-graphs.In the first chapter, we give a brief introduction about the basic concepts, terminologies 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 obtain the result of (K_1,4; 2)-graph as follows:Theorem2.4 Every triangularly connected (K_1,4; 2)-graph with independent claw centers and at least three vertices and without any isolated vertex is full cycle extendable.In the third chapter, we mainly study the paths and cycles of quasi-claw-free graphs and give the following results:Theorem3.2.4 Let G be a connected quasi-claw-free graph of order n≥3. If for any distinct vertices x and y,the inequality 2|N(x)∪N(y)|+ d(x) + d(y)≥2n - 5 holds,then G is traceable.Corollary3.2.5 Let G be a connected quasi-claw-free graph of order n≥3. If for any distinct vertices x and y,the inequality |N(x)∪N(y)|≥2n-5/3 holds,then G is traceable.Theorem3.3.5 Let G be a 2-connected quasi-claw-free graph of order n≥3.If for any distinct vertices x and y,the inequality 2|N(x)N(y)\+d(x) + d(y)≥2n-5 holds,then G is Hamiltonian.Corollary3.3.6 Let G be a 2-connected quasi-claw-free graph of order n≥3.If for any distinct vertices x and y,the inequality |N(x) U N{y)|≥2n-5/3 holds,then G is Hamiltonian.Theorem3.4.2 Let G be a 3-connected quasi-claw-free graph of order n≥3 .If for any independent sets {x₁, x₂, x₃} of three vertices in G,the inequality d(x₁) + d(x₂) + d(x₃)≥n + 1 holds,then G is Hamilton connected.Theorem3.5.3 Let G be a quasi-claw-free graph of order n≥3 with connectivity k. (1)If for any distinct vertices u and v in any independent set S of cardinality k + 1,|N(u)N(v)|≥2n-3k+1/3 holds, then G is hamiltonian.(2)If for any distinct vertices u and v in any independent set S of cardinality k+1,|N(u)N(v)|≥n - k -â–³_S holds, then G is hamiltonian.In the fourth chapter, we mainly give the result of homogeneously traceable:Theorem4.3 If G is 2-connected quasi-claw-free graph of diameter at most 3 without induced subgraph isomorphic H ,then G is homogeneously traceable.