The Chvátal-Erdős condition and pancyclic line-graphs (Q1109045)

The authors determine when a k-connected (k\(\geq 2)\) graph G has a line graph L(G) which is pancyclic; that is, it contains cycles of every length up to the number of vertices in G. If the independence number of G, \(\alpha\) (G), satisfies \(\alpha (G)\geq k+1\) they proved in an earlier paper that L(G) is pancyclic if the degree sum of any \(k+1\) mutually nonadjacent vertices of G is greater than \((k+1)(n+1)/3\). In this paper they show that if \(\alpha (G)\leq k+1\), then L(G) is pancyclic unless G is a cycle \(C_ n\), \(4\leq n\leq 7\), the Petersen graph or one other graph. Working with cases involving chordless cycles or cycles with chords, the authors obtain ranges for lengths of cycles found in G. Principally by undirect methods, they eliminate exceptions, showing the bounds cover all lengths.