Hamiltonicity in Partly claw-free graphs

Hamiltonicity in Partly claw-free graphs

0.00 Avg rating0 Votes
Article ID: iaor200947167
Country: France
Volume: 43
Issue: 1
Start Page Number: 103
End Page Number: 113
Publication Date: Jan 2009
Journal: RAIRO Operations Research
Authors: ,
Abstract:

Matthews and Sumner have proved 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 δ(G)≥(n–2)/3, then G is Hamiltonian. We generalize these results by considering the graphs satisfying the following property: for every vertex vA, 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.

Reviews

Required fields are marked *. Your email address will not be published.