Pancyclicity of claw-free hamiltonian graphs

H. Trommel, H.J. Veldman, A. Verschut

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)
74 Downloads (Pure)

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 languageEnglish
Pages (from-to)781-789
Number of pages9
JournalDiscrete mathematics
Volume197-198
Issue number197/198
DOIs
Publication statusPublished - 1999

Keywords

  • (Hamilton) cycle
  • (Sub)pancyclic
  • IR-74021
  • Claw-free graph
  • METIS-140565
  • Circumference

Fingerprint Dive into the research topics of 'Pancyclicity of claw-free hamiltonian graphs'. Together they form a unique fingerprint.

  • Cite this

    Trommel, H., Veldman, H. J., & Verschut, A. (1999). Pancyclicity of claw-free hamiltonian graphs. Discrete mathematics, 197-198(197/198), 781-789. https://doi.org/10.1016/S0012-365X(99)90147-4