Nonhamiltonian 2-connected claw-free graphs with large 4-degree sum Original Research Article

Let G be a 2-connected claw-free graph on n vertices. Let σk(G) be the minimum degree sum among k-element independent set of vertices in G. It is proved that if σ4(G)⩾n+3 then G is hamiltonian or else G belong to the known family of graphs. This is a generalization of the best known sufficient condition on hamiltonicity in claw-free 2-connected graphs given independently by Liu, Zhang and Broersma. Moreover, it is shown that the problem HAMILTONIAN CYCLE restricted to claw-free graphs G=(V,E) with σ3(G)⩾⌊34(|G|+3)⌋ has polynomial time complexity. This contrasts sharply with known results on NP-completeness among dense graphs.