Abstract
A graph is called \emph{claw-free} if it contains no induced subgraph isomorphic to . Matthews and Sumner proved that a 2-connected claw-free graph is hamiltonian if every vertex of it has degree at least . At the workshop C\&C (Novy Smokovec, 1993), Broersma conjectured the degree condition of this result can be restricted only to end-vertices of induced copies of (the graph obtained from a triangle by adding three disjoint pendant edges). Fujisawa and Yamashita showed that the degree condition of Matthews and Sumner can be restricted only to end-vertices of induced copies of (the graph obtained from a triangle by adding one pendant edge). Our main result in this paper is a characterization of all graphs such that a 2-connected claw-free graph is hamiltonian if each end-vertex of every induced copy of in has degree at least . This gives an affirmative solution of the conjecture of Broersma up to an additive constant.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.