| All graphs considered in this paper are finite, undirected and simple . Let G = (V(G), E(G)) be a graph , where V(G) and E(G] denote the vertex set and edge set of G respectively .A graph G is called almost locally connected if B(G) = {v V(G) : G[N(v)} is not connected } is an independent set and for any v € B(G) , there exist u in V(G) such that G[N(v) U {u}] is connected .If B(G0 = 0 , then we call G is locally connected .Let H is a induced subgraph of G , we say H is a claw of G if H is isomorphic to K1,3, and we call the three-degree vertices of G is claw-centers of this claw.we use D(G) to denote the set of all claw-centers in G . If D(G) = ,G is called a claw-free graph .Claw-free graphs have been a subject of interest of many authors in the recent years.The first motivation for studying properties of claw-free graphs apparently appeared from the Beineke's characterization of line graphs in [4] ,[5].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 the period some first results on hamiltonian properties were proved in [6],[7],[8],[9].Prom then on , more and more authors began to study the problem of hamilton.They studied mainly in the following two aspects : cycle aspect and path aspect .We may obtain some results about cycle in [3]and[10-30]. In this paper we intrest in the following results of cycle: Oberly and Sumner proved the following result in [10]:Theorem A[10] If G is a connected ,locally connected claw-free graph on n > 3 vertices , then G is hamiltonian.Several authors observed that the assumptions of theorem A imply stronger cycle properties . Hendry[3] (and ,later on independently Ambartsumian et al[11] ) proved the following theorem:Theorem B[3],[11] Every connected , locally connected claw-free graph on at least three vertices is fully cycle extendable .We say that G is fully cycle extendable if each vertex of G is on a triangle , and for every cycle C with | V(C] |<| V(G) | there is a cycle C' , such that V(C) C V(C') and | V(C') |=| V(C) | +1 .Apparently , that G is fully cycle extendable which implied hamiltonicity is a stronger result than G is Hamiltonian , So that we study the problem of fully cycle extendable is equate to study the Hamiltonian problem which is one of the four difficult problems in graph theory.Later on , many authors oberserved many other special classes of graphs by improved claw-free graphs because they are not satisfied with the study of claw-free graphs.In this paper almost claw-free graph is interested .Let S C V(G] , if for all u V(G)/S , there is x 6 S such that ux e E(G) , then we call S is a dominate set of G . The dominate set with minimum vertices number is the minimum dominate set of G . We use 7(G) to denote the vertices number of minimum dominate set , If r(G) < k , G is k ~ dominated. Especially, if r(G) < 2 , G is 2 -dominated.A graph G is called almost claw-free graph if "D(G) is independent set , and G[N(v)] is 2 - control" for all v D(G) .About almost claw-free graph , Ryjacek proved the following theorem in [12]. Theorem C[12] Every connected,locally connected K1,4 - free almost claw-free graph is fully cycle extendable.A graph G is called K1,4- free graph if G does not contain an induced subgraph that is isomorphic to K1,4.The paper [10] by Oberly Sumner contains the following conjecture on a generalization to K1,4 - free graphs .Conjecture D[10] If G is a connected,locally r-connected K1,r+2- free graph,then G is hamiltonian.In this paper we introduce two new classes of graphs based on claw-free graph , and study their fully cycle extendable enlightened by the above theorems and conjecture .In the first section , we give a brief foreword and introduction about the basic concepts , terminology and symboles which are used in this paper.In the second section , we introduce the define and one property of quasi-claw-free graph ,and obtain the following theorem and lemma... |
PDF Full Text Request