A variation of a theorem by Pósa

Zoltán Füredi, Alexandr Kostochka, Ruth Luo

Research output: Contribution to journalArticlepeer-review


A graph G is ℓ-hamiltonian if each linear forest F with ℓ edges contained in G can be extended to a hamiltonian cycle of G. We give a sharp upper bound for the maximum number of cliques of a fixed size in a non-ℓ-hamiltonian graph. Furthermore, we prove stability: if a non-ℓ-hamiltonian graph contains almost the maximum number of cliques, then it is a subgraph of one of two extremal graphs.

Original languageEnglish (US)
Pages (from-to)1919-1923
Number of pages5
JournalDiscrete Mathematics
Issue number7
StatePublished - Jul 2019


  • Extremal graph theory
  • Hamiltonian cycles
  • Turán problem

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'A variation of a theorem by Pósa'. Together they form a unique fingerprint.

Cite this