Hamiltonicity in partly claw-free graphs

Abbas, Moncef; Benmeziane, Zineb

RAIRO - Operations Research - Recherche Opérationnelle, Tome 43 (2009) no. 1, pp. 103-113.

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.

Classification : 05C45
Mots clés : graph theory, claw-free graphs, almost claw-free graphs, hamiltonicity, matching

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

[2] D. Bauer and E.F. Schmeichel, Long cycles in tough graphs. Technical Report 8612, Stevens Institute of Technology (1986).

[3] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications. Macmillan, London and Elsevier, New York (1976). | MR

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

[5] H.J. Broersma, Z. Ryjacek and E.F. Schiermeyer, Toughness and Hamiltonicity in almost claw-free graphs. J. Graph theory 21 (1996) 431-439. | MR | Zbl

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

[7] R.J. Faudree, E. Flandrin and Z. Ryjácek, Claw-free graphs - A survey. Discrete Math. 164 (1997) 87-147. | MR | Zbl

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

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

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

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

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

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

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

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

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

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

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