Abstract
A graph G on n vertices is called subpancyclic if it contains cycles of every length k with 3 ≤ k ≤ c(G), where c(G) denotes the length of a longest cycle in G; if moreover c(G) = n, then G is called pancyclic. By a result of Flandrin et al. a claw-free graph (on at least 35 vertices) with minimum degree at least 1/3(n-2) is pancyclic. This degree bound is best possible. We prove that for a claw-free graph to be subpancyclic we only need the degree condition δ > √3n + 1 − 2. Again, this degree bound is best possible. It follows directly that under the same condition a hamiltonian claw-free graph is pancyclic.
Original language | English |
---|---|
Pages (from-to) | 781-789 |
Number of pages | 9 |
Journal | Discrete mathematics |
Volume | 197-198 |
Issue number | 197/198 |
DOIs | |
Publication status | Published - 1999 |
Keywords
- (Hamilton) cycle
- (Sub)pancyclic
- IR-74021
- Claw-free graph
- METIS-140565
- Circumference