Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle

József Balogh, Ping Hu, Bernard Lidický, Florian Pfender

Research output: Contribution to journalArticlepeer-review

Abstract

Let C(n) denote the maximum number of induced copies of 5-cycles in graphs on n vertices. For n large enough, we show that C(n) = a. b. c. d. e + C(a) + C(b) + C(c) + C(d) + C(e), where a+ b+ c+ d+ e = n and a, b, c, d, e are as equal as possible.Moreover, for n a power of 5, we show that the unique graph on n vertices maximizing the number of induced 5-cycles is an iterated blow-up of a 5-cycle.The proof uses flag algebra computations and stability methods.

Original languageEnglish (US)
Pages (from-to)47-58
Number of pages12
JournalEuropean Journal of Combinatorics
Volume52
DOIs
StatePublished - Feb 1 2016

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle'. Together they form a unique fingerprint.

Cite this