Hamiltonicity in Partly claw-free graphs
Université des Sciences et de la Technologie Houari Boumedienne Faculté de Mathématiques, BP 32, El Alia Alger 16111, Algérie; firstname.lastname@example.org
Accepted: 7 July 2008
Matthews and Sumner have proved in  that if G is a 2-connected claw-free graph of order n such that δ(G) ≥ (n-2)/3, then G is Hamiltonian. We say that a graph is almost claw-free if for every vertex v of G, 〈N(v)〉 is 2-dominated and the set A of centers of claws of G is an independent set. Broersma et al.  have proved that if G is a 2-connected almost claw-free graph of order n such that n such that δ(G) ≥ (n-2)/3, then G is Hamiltonian. We generalize these results by considering the graphs satisfying the following property: for every vertex v ∈ A, there exist exactly two vertices x and y of V\A such that N(v) ⊆ N[x] ∪ N[y]. We extend some other known results on claw-free graphs to this new class of graphs.
Mathematics Subject Classification: 05C45
Key words: Graph theory / claw-free graphs / almost claw-free graphs / Hamiltonicity / matching.
© EDP Sciences, ROADEF, SMAI, 2009