Paths And Cycles In Several Graph Families

Paths and cycles are two basic structures of graphs. In fact, many practical prob-lems can be attributed to the problem of paths and cycles.Therefore, the research aboutthem is very active. What is more, the famous Hamilton problem is about paths andcycles of graph in essence. During the recent years,the research mainly focus on thefollowing aspects: hamiltonicity,pancyclism, vertex pancyclism, the longest path(cycle)etc. and we have made great progress. However, we can not deny the fact that it isusually very di?cult to study Hamilton problem in those graphs without any restriction.Then we turn to explore the graphs not containing some forbidden subgraphs such asclaw-free graphs. The first motivation for studying properties of claw-free graphs appar-ently appeared from Beineke's characterization of line graphs in [17]-[18]. However, themain impulse that turned the attention of the graph theory community to the class ofclaw-free graphs was given in late 70s and early 80s.Some famous results about claw-freegraphs can be seen in [2]-[4],[19]-[34].In addition, the definition of claw-free graph hasbeen extended to several larger graph families in di?erent views, such as quasi-claw-freegraphs, almost claw-free graphs, (K_1,4;2)-graphs, DCT graphs etc. A.Ainouche [7] de-fined a new graph family–quasi-claw-free graphs and he also gived several results aboutpaths and cycles in the new graph family. After that, many researchers have done a lotof work to study Hamilton problem in quasi-claw-free graphs[35]-[37]. Almost claw-freegraphs are defined by Z.Ryja′cˇek in [38]. It is also a larger graph family than that ofclaw-free graphs. However, it is very di?cult to extend many good results of claw-freegraphs to almost claw-free graphs. Therefore, Teng Yanyan and You Haiyan gave thedefinition of strongly almost claw-free graphs[5], which contain the family of claw-freegraphs and is contained in the family of almost claw-free graphs. However, many goodresults of claw-free graphs that have not been extended to almost claw-free graphs canbe extended to strongly almost claw-free graphs successfully. The definition of K1,p-extended graphs was put forward when we studied the structure of di?erent graph fami-lies. Let {x1,x2,···,xp} ?V(G)(p ≥ 2) be an independent vertex set such that it satisfiesN(x1) ∩ N(x2) ∩ ··· ∩ N(xp) = φ. If for every u ∈ N(x1) ∩ N(x2) ∩ ··· ∩ N(xp), wehave N[u] ? N[x1] ∪ N[x2] ∪ ···N[xp], then we say that u is a dominating vertex of{x1,x2,···,xp}. The set of all dominating vertices of {x1,x2,···,xp} is said to be a dom-inating vertex set of {x1,x2,···,xp}, which is denoted by D(x1,x2,···,xp). Similarly,theset of all undominating vertices of {x1,x2,···,xp} is said to be an undominating ver-tex set of {x1,x2,···,xp}, which is denoted by D(x1,x2,···,xp). Let {x1,x2,···,xp} beany independent vertex set in V (G)(p ≥ 2). If N(x1) ∩ N(x2) ∩ ··· ∩ N(xp) = φ,thenD(x1,x2,···,xp) = φ, what is more,if for any vertex u of D(x1,x2,···,xp) and any vertexv of D(x1,x2,···,xp), we have uv ∈ E(G), then G is a K1,p-extended graph. By defini-tion,we can easily know that K1,p+1-free graphs are contained in K1,p-extended graphs.In this paper, we mainly study the paths and cycles of claw-free graphs, quasi-claw-freegraphs, strongly almost claw-free graphs and K1,p-extended graphs.In the first chapter, we give a brief introduction about the basic concepts, termi-nologies and symbles which will be used in this paper.In the meantime, we also give somerelated research backgrounds and some known results.In the second chapter, we mainly study the relations among several known results ofclaw-free graphs and give the following results:Theorem 2.5 Every triangularly connected claw-free graph without isolated verticesis also quasilocally connected claw-free.Corollary 2.6 The result of "Every triangularly connected claw-free graph G with|E(G)| ≥ 3 and without isolated vertices is vertex pancyclic" is contained in that of"Every quasilocally connected claw-free graph with |V (G)| ≥ 3 is vertex pancyclic".In the third chapter,we mainly obtain the results as follows.Theorem 3.1.3 If G is a connected quasi-claw-free graph, then G has a path whichis either hamiltonian or of length at least 2δ(G) + 2.Theorem 3.1.4 If G is a connected quasi-claw-free graph with δ(G)≥ (|G| ? 2)/3,then G has a hamiltonian path.Theorem 3.4.2 Every triangularly connected quasi-claw-free graph G with |E(G)| ≥3 and without isolated vertices is vertex pancyclic.Theorem 3.5.4 Every quasilocally connected quasi-claw-free graph of order n≥ 3is vertex pancyclic.Theorem 3.5.5 Let G be a quasi-claw-free graph of connectivity κ(G) ≥ 2 andM(G) = {x ∈ V (G) : N(x) is connected}. Suppose that M(G) is a dominating set ofG and M(G) has r components. If r ≤ κ(G), then G is hamiltonian.Theorem 3.6.1 Let G be a connected almost locally connected quasi-claw-freegraph with |V (G)| ≥ 3. If δ(G) ≥ 3, then G is vertex pancyclic and the lower bound ofδ(G) is best possible.Theorem 3.7.1 Let G be a quasi-claw-free graph and let x be an eligible vertex ofG.Let G be a local completion of G at x. Then the graph G is a quasi-claw-free graphbut it is not sure that G is a claw-free graph .Corollary 3.7.2 Let G be a quasi-claw-free graph. Then cl(G) is still a quasi-claw-free graph.Theorem 3.7.3 Let G be a quasi-claw-free graph. Then cl(G) is well defined.In the fourth chapter, we mainly improve some corresponding results of R. J. Faudree,R. J. Gould etc.Theorem 4.1.2 If G is a connected strongly almost claw-free graph, then G has apath which is either hamiltonian or of length at least 2δ(G) + 2.Theorem 4.1.3 If G is a connected strongly almost claw-free graph with δ(G)≥(|G| ? 2)/3, then G has a hamiltonian path.Theorem 4.1.4 Let G be a 2-connected strongly almost claw-free graph. If NC ≥(|G| ? 1)/2,then G has a hamiltonian path.Theorem 4.2.4 Every triangularly connected strongly almost claw-free graph with-out isolated vertices is both fully cycle extendable and vertex pancyclic orderable.In the last chapter,we define a new graph family–K1,p-extended graph and give thefollowing result.Theorem 5.2.1 Every triangularly connected K1,2-extended graph without isolatedvertices is fully cycle extendable.