Article
Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle
European Journal of Combinatorics
Document Type
Article
Disciplines
Publication Version
Accepted Manuscript
Publication Date
2-1-2016
DOI
10.1016/j.ejc.2015.08.006
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.
Creative Commons License
Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International
Copyright Owner
Elsevier Ltd.
Copyright Date
2015
Language
en
File Format
application/pdf
Citation Information
József Balogh, Ping Hu, Bernard Lidický and Florian Pfender. "Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle" European Journal of Combinatorics Vol. 52, Part A (2016) p. 47 - 58 Available at: http://works.bepress.com/bernard-lidicky/34/
This is a manuscript of an article published as Balogh, József, Ping Hu, Bernard Lidický, and Florian Pfender. "Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle." European Journal of Combinatorics 52, Part A (2016): 47-58. doi: 10.1016/j.ejc.2015.08.006. Posted with permission.