The Chvátal-Erdős condition and pancyclic line-graphs
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.
scientific article; zbMATH DE number 4068913
scientific article