2018/04/16 by Zoltán Füredi, Furedi, Zoltan, Alexandr Kostochka +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · doi:10.48550/arxiv.1804.05829
openalex publication_date 2018/04/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph G is ℓ-hamiltonian if for any linear forest F of G with ℓ edges, F 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 for the bound: if a non-ℓ-hamiltonian graph contains almost the maximum number of cliques, then it must be a subgraph of one of two examples.