Hostname: page-component-745bb68f8f-v2bm5 Total loading time: 0 Render date: 2025-02-06T22:31:00.738Z Has data issue: false hasContentIssue false
  • English
  • Français

Extremal Numbers for Odd Cycles

Published online by Cambridge University Press:  01 December 2014

ZOLTAN FÜREDI  and
DAVID S. GUNDERSON
ZOLTAN FÜREDI
Affiliation:
Rényi Institute of Mathematics, Hungarian Academy of Sciences, Reáltanoda utca 13–15, H-1053, Budapest, Hungary (e-mail: z-furedi@illinois.edu, furedi.zoltan@renyi.mta.hu)
DAVID S. GUNDERSON
Affiliation:
Department of Mathematics, University of Manitoba, 521 Machray Hall, Winnipeg, Manitoba R3T 2N2, Canada (e-mail: David.Gunderson@umanitoba.ca)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We describe the C2k+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, C2k+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 n0(C2k+1) is 4k in the classical theorem of Simonovits, from which the unique extremal graph is the bipartite Turán graph.

Keywords

Primary 05C35Secondary 05D99
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 24 , Special Issue 4: Oberwolfach Special Issue Part 1 , July 2015 , pp. 641 - 645
Copyright
Copyright © Cambridge University Press 2014 

References

[1]Bollobás, B. (1979) Extremal Graph Theory, Academic Press.CrossRefGoogle Scholar
[2]Bondy, J. A. (1971) Pancyclic graphs I. J. Combin. Theory Ser. B 11 80–84.CrossRefGoogle Scholar
[3]Bondy, J. A. (1971) Large cycles in graphs. Discrete Math. 1 121–132.CrossRefGoogle Scholar
[4]Brandt, S. (1997) A sufficient condition for all short cycles. In 4th Twente Workshop on Graphs and Combinatorial Optimization. Discrete Appl. Math. 79 63–66.CrossRefGoogle Scholar
[5]Dzido, T. (2013) A note on Turán numbers for even wheels. Graphs Combin. 29 1305–1309.CrossRefGoogle Scholar
[6]Erdős, P. and Gallai, T. (1959) On maximal paths and circuits of graphs. Acta Math. Acad. Sci. Hungar. 10 337–356.CrossRefGoogle Scholar
[7]Faudree, R. J. and Schelp, R. H. (1975) Path Ramsey numbers in multicolorings. J. Combin. Theory Ser. B 19 150–160.CrossRefGoogle Scholar
[8]Füredi, Z. and Simonovits, M. (2013) The history of degenerate (bipartite) extremal graph problems. In Erdős Centennial (Lovász, L.et al., eds), Vol. 25 of Bolyai Society Mathematical Studies, pp. 167–262.CrossRefGoogle Scholar
[9]Kopylov, G. N. (1977) Maximal paths and cycles in a graph. Dokl. Akad. Nauk SSSR 234 19–21. (English translation in Soviet Math. Dokl. 18 (1977) 593–596.)Google Scholar
[10]Mantel, W. (1907) Solution to Problem 28, by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh, and W. A. Wythoff. Wiskundige Opgaven 10 60–61.Google Scholar
[11]Simonovits, M. (1974) Extremal graph problems with symmetrical extremal graphs: Additional chromatic conditions. Discrete Math. 7 349–376.CrossRefGoogle Scholar
[12]Turán, P. (1941) Eine Extremalaufgabe aus der Graphentheorie (in Hungarian). Math. Fiz Lapok 48 436–452.Google Scholar
[13]Turán, P. (1954) On the theory of graphs. Colloq. Math. 3 19–30.CrossRefGoogle Scholar
[14]Woodall, D. R. (1972) Sufficient conditions for circuits in graphs. Proc. London Math. Soc. (3) 24 739–755.CrossRefGoogle Scholar
[15]Woodall, D. R. (1976) Maximal circuits of graphs I. Acta Math. Acad. Sci. Hungar. 28 77–80.CrossRefGoogle Scholar