The Chvátal-Erdős condition and pancyclic line-graphs
type: Item
instance of: scholarly article
title: The Chvátal-Erdős condition and pancyclic line-graphs
zbMATH Open document ID: 0655.05040
DOI: 10.1016/0012-365X(87)90115-4
author: Abdelhamid Benhocine
author: Jean-Luc Fouquet
published in: Discrete Mathematics
publication date: 1987-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 4068913
zbMATH Keywords: pancyclic graph
zbMATH Keywords: line graph
reviewed by: Norman F. Quimpo
MaRDI profile type: Publication
cites work: Q5184942
cites work: Pancyclic and panconnected line graphs
cites work: Q4041607
cites work: Pancyclic graphs. II
cites work: A note on Hamiltonian circuits
cites work: On Eulerian and Hamiltonian Graphs and Line Graphs
Recommended article: Pancyclism in Chvátal-Erdős' graphs
Recommended article: Chvátal-Erdös condition and pancyclism
Recommended article: The Chvátal-Erdös condition for cycles in triangle-free graphs
Recommended article: A Chvátal--Erdős type condition for pancyclability
Recommended article: The Chvátal-Erdős condition for panconnectivity of triangle-free graphs
Recommended article: Chvátal-Erdős conditions for paths and cycles in graphs and digraphs. A survey
Recommended article: A chvátal–erdős type condition for hamiltonian graphs
Recommended article: Q3487369
Recommended article: A Chvátal-Erdős condition for Hamilton cycles in digraphs
Recommended article: A de Bruijn-Erdős theorem for chordal graphs
description: scientific article; zbMATH DE number 4068913