论文部分内容阅读
A graph is called claw-free if it contains no induced copy of the claw (K1,3).Matthews and Sumner proved that a 2-connected claw-free graph G is hamiltonian if every vertex of it has degree at least (|V(G)|-2)/3.On 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 N (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 Z1 (the graph obtained from a triangle by adding one pendant edge).Our main result in this paper is a characterization of all graphs H such that a 2-connected claw-free graph G is hamiltonian if each end-vertex of every induced copy of H in G has degree at least |V(G)|/3 + 1.This gives an affirmation of the conjecture of Broersma up to an additive constant.