Matthews and Sumner have proved in [10] that if $G$ is a 2-connected claw-free graph of order $n$ such that $\delta \left(G\right)\ge (n-2)/3$, then $G$ is hamiltonian. We say that a graph is almost claw-free if for every vertex $v$ of G, $\langle N\left(v\right)\rangle $ is 2-dominated and the set $A$ of centers of claws of $G$ is an independent set. Broersma et al. [5] have proved that if $G$ is a 2-connected almost claw-free graph of order $n$ such that $\delta \left(G\right)\ge (n-2)/3$, then $G$ is hamiltonian. We generalize these results by considering the graphs satisfying the following property: for every vertex $v\in A$, there exist exactly two vertices $x$ and $y$ of $V\setminus A$ such that $N\left(v\right)\subseteq N\left[x\right]\cup N\left[y\right]$. We extend some other known results on claw-free graphs to this new class of graphs.

Keywords: graph theory, claw-free graphs, almost claw-free graphs, hamiltonicity, matching

@article{RO_2009__43_1_103_0, author = {Abbas, Moncef and Benmeziane, Zineb}, title = {Hamiltonicity in partly claw-free graphs}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {103--113}, publisher = {EDP-Sciences}, volume = {43}, number = {1}, year = {2009}, doi = {10.1051/ro/2009007}, mrnumber = {2502327}, zbl = {1158.05324}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ro/2009007/} }

TY - JOUR AU - Abbas, Moncef AU - Benmeziane, Zineb TI - Hamiltonicity in partly claw-free graphs JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2009 SP - 103 EP - 113 VL - 43 IS - 1 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro/2009007/ DO - 10.1051/ro/2009007 LA - en ID - RO_2009__43_1_103_0 ER -

%0 Journal Article %A Abbas, Moncef %A Benmeziane, Zineb %T Hamiltonicity in partly claw-free graphs %J RAIRO - Operations Research - Recherche Opérationnelle %D 2009 %P 103-113 %V 43 %N 1 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro/2009007/ %R 10.1051/ro/2009007 %G en %F RO_2009__43_1_103_0

Abbas, Moncef; Benmeziane, Zineb. Hamiltonicity in partly claw-free graphs. RAIRO - Operations Research - Recherche Opérationnelle, Volume 43 (2009) no. 1, pp. 103-113. doi : 10.1051/ro/2009007. http://archive.numdam.org/articles/10.1051/ro/2009007/

[1] Long cycles in graphs with large degree sums. Discrete Math. 79 (1989/90) 59-70. | MR | Zbl

et al.,[2] Long cycles in tough graphs. Technical Report 8612, Stevens Institute of Technology (1986).

and ,[3] Graph Theory with Applications. Macmillan, London and Elsevier, New York (1976). | MR

and ,[4] Hamilton cycles in graphs and related topics. Ph.D. Thesis, University of Twente (1988).

,[5] Toughness and Hamiltonicity in almost claw-free graphs. J. Graph theory 21 (1996) 431-439. | MR | Zbl

, and ,[6] Tough graphs and Hamiltonian circuits. Discrete Math. 5 (1973) 215-228. | MR | Zbl

,[7] Claw-free graphs - A survey. Discrete Math. 164 (1997) 87-147. | MR | Zbl

, and ,[8] Hamiltonism and claws. Ars Combinatoria 29C (1990) 77-89. | MR | Zbl

and ,[9] Hamiltonicity in 2-connected graphs with claws. Discrete Math. 183 (1998) 223-236. | MR | Zbl

, and ,[10] Hamiltonian results in K${}_{1,3}$ -free graphs. J. Graph Theory 8 (1984) 139-146. | MR | Zbl

and ,[11] Longest paths and cycles in K${}_{1,3}$-free graphs. J. Graph Theory 9 (1985) 269-277. | MR | Zbl

and ,[12] Hamilton connected graphs. J. Math. Pure Appl. 42 (1963) 21-27. | MR | Zbl

,[13] Almost claw-free graphs. J. Graph Theory 18 (1994) 469-477. | MR | Zbl

,[14] On a closure concept in claw-free graphs. J. Combinat. Theory B70 (1997) 217-224. | MR | Zbl

,[15] Graphs with 1-factors. Proceeding of the American Mathematical Society (1974) 8-12. | MR | Zbl

,[16] 1-factors and antifactors sets. J. London Math. Soc. 213 (1976) 351-359. | MR | Zbl

,[17] Reflections on graph theory. J Graph Theory 10 (1986) 309-324. | MR | Zbl

,[18] Hamilton cycles in claw-free graphs. J. Graph Theory 12 (1988) 209-216. | MR | Zbl

,*Cited by Sources: *