REAL

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

[img]
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.

Item Type: Article
Subjects: Q Science / természettudomány > QA Mathematics / matematika
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 17 Feb 2016 10:25
Last Modified: 17 Feb 2016 10:25
URI: http://real.mtak.hu/id/eprint/33624

Actions (login required)

Edit Item Edit Item