Pancyclicity of claw-free Hamiltonian graphs (Q1292881)

A graph \(G= (V,E)\) on \(n\) vertices is pancyclic if it has cycles of all lengths \(3,4,\dots, n\) and subpancyclic if it has cycles of all lengths \(3,4,\dots, c(G)\), where \(c(G)\) denotes the length of a longest cycle in \(G\). A graph is claw-free if it does not contain an induced copy \(K_{1,3}\). The authors prove that if the minimum degree \(\delta(G)\) of a claw-free graph \(G\) on \(n\) vertices is at least \(\sqrt{3n+1}-1\) then \(G\) is subpancyclic. They also show that this degree bound is best possible. This immediately implies that if a Hamiltonian claw-free graph \(G\) has minimum degree at least \(\sqrt{3n+1}-1\) then \(G\) is pancyclic. In contrast, Flandrin et al. have shown that in order to guarantee that a claw-free graph (on at least 35 vertices) is Hamiltonian one needs to require \(\delta(G)\geq{1\over 3}(n- 2)\).