Item request has been placed! ×
Item request cannot be made. ×
loading  Processing Request

Chvátal-Erdős condition for pancyclicity

Item request has been placed! ×
Item request cannot be made. ×
loading   Processing Request
Read More Add to Saved list
  • Additional Information
    • Publication Information:
      Association for Mathematical Research
    • Publication Date:
      2024
    • Collection:
      ETH Zürich Research Collection
    • Abstract:
      An $n$-vertex graph is Hamiltonian if it contains a cycle that covers all of its vertices and it is pancyclic if it contains cycles of all lengths from $3$ up to $n$. A celebrated meta-conjecture of Bondy states that every non-trivial condition implying Hamiltonicity also implies pancyclicity (up to possibly a few exceptional graphs). We show that every graph $G$ with $κ(G) > (1+o(1)) α(G)$ is pancyclic. This extends the famous Chvátal-Erdős condition for Hamiltonicity and proves asymptotically a $30$-year old conjecture of Jackson and Ordaz. ; ISSN:2998-4114
    • File Description:
      application/application/pdf
    • Relation:
      info:eu-repo/grantAgreement/SNF/Projekte MINT/196965; http://hdl.handle.net/20.500.11850/694210
    • Accession Number:
      10.3929/ethz-b-000694210
    • Online Access:
      https://doi.org/20.500.11850/69421010.3929/ethz-b-00069421010.56994/JAMR.002.001.001
      https://hdl.handle.net/20.500.11850/694210
      https://doi.org/10.3929/ethz-b-000694210
    • Rights:
      info:eu-repo/semantics/openAccess ; http://creativecommons.org/licenses/by-nc/4.0/ ; Creative Commons Attribution-NonCommercial 4.0 International
    • Accession Number:
      edsbas.D59F2464