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

DOI10.1016/0012-365X(87)90115-4MaRDI QIDQ1109045zbMATH OpenFDO

Authors Abdelhamid Benhocine, Jean-Luc Fouquet

Publication date 1987

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(87)90115-4

zbMATH Keywords

line graphpancyclic graph

Mathematics Subject Classification ID

Paths and cycles (05C38)

Review text

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.

Recommendations

• Pancyclism in Chvátal-Erdős' graphs
• Chvátal-Erdös condition and pancyclism
• The Chvátal-Erdös condition for cycles in triangle-free graphs
• A Chvátal--Erdős type condition for pancyclability
• The Chvátal-Erdős condition for panconnectivity of triangle-free graphs
• Chvátal-Erdős conditions for paths and cycles in graphs and digraphs. A survey
• A chvátal–erdős type condition for hamiltonian graphs
• scientific article; zbMATH DE number 4160763
• A Chvátal-Erdős condition for Hamilton cycles in digraphs
• A de Bruijn-Erdős theorem for chordal graphs

Cites work

• A note on Hamiltonian circuits
• scientific article; zbMATH DE number 3455294 (Why is no real title available?)
• scientific article; zbMATH DE number 3893240 (Why is no real title available?)
• On Eulerian and Hamiltonian Graphs and Line Graphs
• Pancyclic and panconnected line graphs
• Pancyclic graphs. II

Cited in

(10)

• The ubiquitous Petersen graph
• A new Chvátal type condition for pancyclicity
• The Chvátal-Erdős condition for panconnectivity of triangle-free graphs
• Chvátal-Erdős conditions for paths and cycles in graphs and digraphs. A survey
• scientific article; zbMATH DE number 3952821 (Why is no real title available?)
• Pancyclic and panconnected line graphs
• The Chvátal-Erdős condition for a graph to have a spanning trail
• Pancyclism in Chvátal-Erdős' graphs
• A Chvátal--Erdős type condition for pancyclability
• The Chvàtal-Erdős condition for supereulerian graphs and the Hamiltonian index

This page was built for publication: The Chvátal-Erdős condition and pancyclic line-graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1109045)