Search

Broersma and Veldman proved that every 2-connected claw-free and P -free graph is hamiltonian. Chen et al. extended this result by proving every 2-connected claw-heavy and P -free graph is hamiltonian. On the other hand, Li et al. constructed a class of 2-connected graphs which are claw-heavy and P -o-heavy but not hamiltonian. In this paper, we further give some Ore-type degree conditions restricting to induced copies of P of a 2-connected claw-heavy graph that can guarantee the graph to be hamiltonian. This improves some previous related results. [ABSTRACT FROM AUTHOR]

A graph is called claw-free if it contains no induced subgraph isomorphic to K. 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. At the workshop Camp;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 Z (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 affirmative solution of the conjecture of Broersma up to an additive constant. [ABSTRACT FROM AUTHOR]

A graph G is called claw-o-heavy if every induced claw ( $$K_{1,3}$$ ) of G has two end-vertices with degree sum at least | V( G)|. For a given graph S, G is called S-f-heavy if for every induced subgraph H of G isomorphic to S and every pair of vertices $$u,v\in V(H)$$ with $$d_H(u,v)=2,$$ there holds $$\max \{d(u),d(v)\}\ge |V(G)|/2.$$ In this paper, we prove that every 2-connected claw- o-heavy and $$Z_3$$ - f-heavy graph is hamiltonian (with two exceptional graphs), where $$Z_3$$ is the graph obtained by identifying one end-vertex of $$P_4$$ (a path with 4 vertices) with one vertex of a triangle. This result gives a positive answer to a problem proposed Ning and Zhang (Discrete Math 313:1715-1725, ), and also implies two previous theorems of Faudree et al. and Chen et al., respectively. [ABSTRACT FROM AUTHOR]