Maximum density of an induced 5-cycle is achieved by an iterated blow-up of a 5-cycle

preprint2014arXivOpen access

Abstract

Let C(n)C(n) denote the maximum number of induced copies of 5-cycles in graphs on nn vertices. For nn large enough, we show that C(n)=a⋅b⋅c⋅d⋅e+C(a)+C(b)+C(c)+C(d)+C(e)C(n)=a\cdot b\cdot c \cdot d \cdot e + C(a)+C(b)+C(c)+C(d)+C(e), where a+b+c+d+e=na+b+c+d+e = n and a,b,c,d,ea,b,c,d,e are as equal as possible. Moreover, if nn is a power of 5, we show that the unique graph on nn vertices maximizing the number of induced 5-cycles is an iterated blow-up of a 5-cycle.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.