Journal or Book Title
European Journal of Combinatorics
52, Part A
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.
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.
Balogh, József; Hu, Ping; Lidický, Bernard; and Pfender, Florian, "Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle" (2016). Mathematics Publications. 119.