Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 16 min ago
PreprintarXiv licencearXiv

Logarithmic Circumference In Tough Graphs

  • Levi Segal
  • Jacques Verstraete
Open at sourcePDFDOICite

Abstract

For every real t>0, we prove that every $2$-connected t-tough graph contains a cycle of length at least ℓ whenever n ≤ ℓ(1 + 1/t)⌊ ℓ/2⌋ − 1. This establishes the logarithmic bound conjectured by Broersma, van den Heuvel, Jung, and Veldman.

Related

  1. Polynomial Length Cycles In Tough Graphs
    Levi Segal, Jacques Verstraete
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Degree sequence condition for pancyclicity in tough graphs
    Songling Shan, Zachary Warren
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Long Cycles in 2-Connected Tough Graphs
    Songling Shan
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Spectral radius and size conditions for 1-tough balanced bipartite graphs to contain a k-factor with k≥ 3
    Jinxuan Ren, Jiayao Song, Ligong Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Linear circumference in vertex-transitive graphs
    Jie Ma, Ziyuan Zhao
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{segal2026logarithmic,
  title = {{Logarithmic Circumference In Tough Graphs}},
  author = {Levi Segal and Jacques Verstraete},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.16083},
  eprint = {2609.16083},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.16083},
}
RIS
TY  - UNPB
TI  - Logarithmic Circumference In Tough Graphs
AU  - Levi Segal
AU  - Jacques Verstraete
PY  - 2026
DA  - 2026/09/16
PB  - arXiv
DO  - 10.48550/arxiv.2609.16083
UR  - https://arxiv.org/abs/2609.16083
AB  - For every real t>0, we prove that every $2$-connected t-tough graph contains a cycle of length at least ℓ whenever n ≤ ℓ(1 + 1/t)^⌊ ℓ/2⌋ − 1. This establishes the logarithmic bound conjectured by Broersma, van den Heuvel, Jung, and Veldman.
ER  -