TY - JOUR
T1 - Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle
AU - Balogh, József
AU - Hu, Ping
AU - Lidický, Bernard
AU - Pfender, Florian
N1 - Publisher Copyright:
© 2015 Elsevier Ltd.
PY - 2016/2/1
Y1 - 2016/2/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84942066416&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84942066416&partnerID=8YFLogxK
U2 - 10.1016/j.ejc.2015.08.006
DO - 10.1016/j.ejc.2015.08.006
M3 - Article
AN - SCOPUS:84942066416
SN - 0195-6698
VL - 52
SP - 47
EP - 58
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
ER -