2021/02/12 by Bernard Lidický, Lidický, Bernard, Connor Mattes +3 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2102.06773
openalex publication_date 2021/02/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
We determine the maximum number of induced copies of a 5-cycle in a graph on n vertices for every n. Every extremal construction is a balanced iterated blow-up of the 5-cycle with the possible exception of the smallest level where for n=8, the Möbius ladder achieves the same number of induced 5-cycles as the blow-up of a 5-cycle on 8 vertices. This result completes work of Balogh, Hu, Lidický, and Pfender [Eur. J. Comb. 52 (2016)] who proved an asymptotic version of the result. Similarly to their result, we also use the flag algebra method but we extend its use to small graphs.