Hamilton Problem Of Strongly Almost Claw-free Graphs And K_1,2-extended Graphs

The problem on hamiltonicity of graphs is a very important problem in graph theory and the research is also very active. There are a lot of papers dealing with this problem each year. However. it is always very difficult to study the problem on hamiltonicity in those graphs without any restriction. Therefore, recently, researches on hamiltonicity have been on mainly in some special fields. Some advances on hamiltonicity can be referred to [23]-[25]. The first motivation for studying properties of claw-free graphs apparently appeared from the Beineke's characterization of line graphs in [10]-[11]. 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. During this period the matching properties of such graphs were observed in [12]-[14], and first results on hamiltonian properties were proved in [15]-[18]. However, probably more importantly, were the observations that the determination of the independence number is polynomial (see [19]-[20]) and that the Berge's Perfect Graph Conjecture holds (see [21]) in claw-free graphs. The paper of [22] is a survey about claw-free graphs. Some other good results of claw-free graphs can be referred to [37]-[50]. In fact, traceability, pancyclism, fully cycle extensibility and hamiltonian connectedness are also hamiltonian problem of graphs in essence.During recent years, the concept of claw-free graphs has also been extended to some other larger graph families, such as quasi-claw-free graphs, almost claw-free graphs, (K_1,4;2)-graphs, DCT graphs and so on. Some advances about quasi-claw-free graphs, almost claw-free graphs and (K_1,4;2)-graphs can be referred to [3], [26]-[35] respectively. The definition of strongly almost claw-free graphs was put forward by Teng Yanyan and You Haiyan in [6]. It is also a larger graph family than that of claw-free graphs. However, it is contained in the familty of almost claw-free graphs. But many good results in claw-free graphs that are very difficult to be extended to almost claw-free graphs can be extended to strongly almost claw-free graphs successfully.The definition of iifi^-extended graphs was put forward when we studied the structure of different graph families. Let {xi,x2l---,xp} CV(G)(p > 2) be an independent vertex set such that it satisfies N(xi) D N(x2) n ? ? ? n N(xp) ^ . If for every u € N(xi) D N(x2) n ? ? ? D N(xp), we have N[u) C N[Xl] U N[x2] U ? -'N[xp], then we say that u is a dominating vertex of {xi,x2, ? ? ? ,xp}. The set of all dominating vertices of {xi,x2,---,xp} is said to be a dominating vertex set of {xi,x2,? ? ?,xp}, which is denoted by D(xi,x2,->-,xp). Similarly,the set of all undominating vertices of {xx,x2,■ ? ■,xp} is said to be an undominating vertex set of {xi,x2,-- -,xp}, which is denoted by D(xi,x2,??-,xp). Let {xi,x2,---,xp} be any independent vertex set in V(G)(p > 2). If N(Xl) n N(x2) n ? ? ? n N(xp) ^ ,then D(xu x2, ■ ■ ?,xp) ^ fa what is more,if for any vertex u of D(x\,x2, ? ? ■,xp) and any vertex v of T)(x\,x2, ? - ?,xp), we have uv e E(G), then G is a .K^p-extended graph. By definition,we can easily know that JFTi^+i-free graphs are contained in KiiP-extended graphs. What is more, Jffij3-free graphs are contained in iiTi^-extended graphs. In another word, we can easily know that claw-free graphs are contained in ifi^-extended graphs.In this paper, we mainly study vertex pancyclism in strongly almost claw-free graphs and fully cycle extensibility in i^i^-extended graphs.In the first chapter, we give a brief introduction about the basic concepts, terminologies and symbles 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 vertex pancyclism in strongly almost claw-free graphs and prove the two results as follows.Theorem 2.2.3 Let G be a connected,strongly almost claw-free graph such that every induced Z\ of G satisfies <￡z,(c,&i) or $Zl(c,&2).If S(G) > 3, then G is vertex pancyclic. (See Z\ in Fig.2.1).Theorem 2.3.3 Let G be a 2-connected,strongly almost claw-free graph such that every induced Z2 of G satisfies ^z2(°i>^i) and ^Zifauh)- If $(G) > 3, then G is vertex pancyclic. (See Z2 in Fig.2.2).Then in fact, we improve the results of H.J.Broersma, H.J.Veldman[36], Mingchu Li[2] respectively.In the third chapter,we mainly study fully cycle extensibility of i^lj2-extended graphsin different conditions, and improve the results of D.Oberly, D.Sumner[7], L.Clark[8], G.R.Hendry[9] respectively, we obtain the following three results.Theorem 3.2.1 Let G be a connected /^-extended graph with at least three vertices and C be a r-cycle in G where r satisfies that 3 < r < \V(G)\. If C has a bridge B such that Nc(B) contains a locally connected vertex, then C has an extended cycle inTheorem 3.3.4 Every quasilocally connected ifi^-extended graph with at least three vertices is fully cycle extendable.Theorem 3.4.1 Let G be a connected and almost locally connected i^i graph with at least three vertices. If 8(G) > 3, then G is fully cycle extendable.