Extremal Numbers for Odd Cycles

Füredi, Zoltán and Gunderson, David S. (2015) Extremal Numbers for Odd Cycles. COMBINATORICS PROBABILITY AND COMPUTING, 24. pp. 641-645. ISSN 0963-5483

Preview

Text 1310.6766v1.pdf Download (100kB) | Preview

Abstract

We describe the C 2k+1-free graphs on n vertices with maximum number of edges. The extremal graphs are unique for n ∉ {3k − 1, 3k, 4k − 2, 4k − 1}. The value of ex(n, C 2k+1) can be read out from the works of Bondy [3], Woodall [14], and Bollobás [1], but here we give a new streamlined proof. The complete determination of the extremal graphs is also new. We obtain that the bound for n 0(C 2k+1) is 4k in the classical theorem of Simonovits, from which the unique extremal graph is the bipartite Turán graph.

Actions (login required)

Edit Item