Campus Units

Mathematics

Document Type

Article

Publication Version

Submitted 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)C(n)denote the maximum number of induced copies of 55-cycles in graphs on nnvertices. For nnlarge enough, we show that C(n)=a⋅b⋅c⋅d⋅e+C(a)+C(b)+C(c)+C(d)+C(e)C(n)=a⋅b⋅c⋅d⋅e+C(a)+C(b)+C(c)+C(d)+C(e), where a+b+c+d+e=na+b+c+d+e=nand a,b,c,d,ea,b,c,d,eare as equal as possible.

Moreover, for nna power of 5, we show that the unique graph on nnvertices maximizing the number of induced 55-cycles is an iterated blow-up of a 5-cycle.

The proof uses flag algebra computations and stability methods.

Comments

This article is 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 (2016): 47-58.doi: https://doi.org/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 Inc.

Language

en

File Format

application/pdf

Published Version

Share

COinS