Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-09T23:15:31.827Z Has data issue: false hasContentIssue false
  • English
  • Français

The Maximum Number of Triangles in C2k+1-Free Graphs

Published online by Cambridge University Press:  02 February 2012

ERVIN GYŐRI  and
HAO LI
ERVIN GYŐRI
Affiliation:
Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest H-1364, PO box 127, Hungary (e-mail: ervin@renyi.hu)
HAO LI
Affiliation:
Laboratoire de Recherche en Informatique, UMR 8623, CNRS–Université de Paris-Sud, 91405 Orsay CEDEX, France and School of Mathematics and Statistics, Lanzhou University, Lanzhou 730000, China (e-mail: li@lri.fr)
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.

Upper and lower bounds are proved for the maximum number of triangles in C2k+1-free graphs. The bounds involve extremal numbers related to appropriate even cycles.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 1-2: Honouring the Memory of Richard H. Schelp , March 2012 , pp. 187 - 191
Copyright
Copyright © Cambridge University Press 2012

References

[1]Bollobás, B. (2000) Modern Graph Theory, Springer.Google Scholar
[2]Bollobás, B. and Győri, E. (2008) Triangles vs. pentagons. Discrete Math. 308 4332–4336.Google Scholar
[3]Bondy, J. A. and Simonovits, M. (1974) Cycles of even length in graphs. J. Combin. Theory Ser. B 16 97–105.Google Scholar
[4]Erdős, P. On some problems in graph theory, combinatorial analysis and combinatorial number theory. In Graph Theory and Combinatorics (Bollobás, B., ed.), pp. 1–17.Google Scholar
[5]Erdős, P. and Gallai, T. (1959) On maximal paths and circuits of graphs. Acta Math. Acad. Sci. Hungar. 10 337–356.CrossRefGoogle Scholar
[6]Grzesik, A. On the maximum number of C 5's in a triangle-free graph. arXiv:1102.0962Google Scholar
[7]Győri, E. (1989) On the number of C 5's in a triangle-free graph. Combinatorica 9 101–102.CrossRefGoogle Scholar
[8]Hatami, H., Hladky, J., Kral, D., Norine, S. and Razborov, A. On the number of pentagons in triangle-free graphs. arXiv:1102.1634v2Google Scholar