Campus Units

Mathematics

Document Type

Article

Publication Version

Accepted Manuscript

Publication Date

2-2016

Journal or Book Title

European Journal of Combinatorics

Volume

52, Part A

First Page

47

Last Page

58

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.

Comments

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.

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Copyright Owner

Elsevier Ltd.

Language

en

File Format

application/pdf

Published Version

Share

COinS