On the maximum number of odd cycles in graphs without smaller odd cycles
Main Article Content
Abstract
We prove that for each odd integer $k \geq 7$, every graph on $n$ vertices without odd cycles of length less than $k$ contains at most $(n/k)^k$ cycles of length~$k$. This generalizes the previous results on the maximum number of pentagons in triangle-free graphs, conjectured by Erd\H os in 1984, and asymptotically determines the generalized Tur\'an number $\mathrm{ex}(n,C_k,C_{k-2})$ for odd $k$. In contrast to the previous results on the pentagon case, our proof is not computer-assisted.
Article Details
How to Cite
Grzesik, A., & Kielak, B.
(2019).
On the maximum number of odd cycles in graphs without smaller odd cycles.
Acta Mathematica Universitatis Comenianae, 88(3), 755-758.
Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1234/723
Issue
Section
EUROCOMB 2019