Hamiltonicity in partly claw-free graphs

Abbas, Moncef ; Benmeziane, Zineb

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

Résumé

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.

Détail

DOI : 10.1051/ro/2009007

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