Hostname: page-component-745bb68f8f-f46jp Total loading time: 0 Render date: 2025-02-06T19:05:03.824Z Has data issue: false hasContentIssue false
  • English
  • Français

The Minimum Number of Triangular Edges and a Symmetrization Method for Multiple Graphs

Published online by Cambridge University Press:  23 January 2017

ZOLTÁN FÜREDI  and
ZEINAB MALEKI
ZOLTÁN FÜREDI
Affiliation:
Alfréd Rényi Institute of Mathematics, 13–15 Reáltanoda Street, 1053 Budapest, Hungary (e-mail: z-furedi@illinois.edu)
ZEINAB MALEKI
Affiliation:
Department of Mathematical Sciences, Isfahan University of Technology, Isfahan 84156-83111, Iran (e-mail: zmaleki@math.iut.ac.ir)
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 give an asymptotic formula for the minimum number of edges contained in triangles among graphs with n vertices and e edges. Our main tool is a generalization of Zykov's symmetrization method that can be applied to several graphs simultaneously.

Keywords

Primary 05C35Secondary 05C2205D99
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 4 , July 2017 , pp. 525 - 535
Copyright
Copyright © Cambridge University Press 2017 

References

[1] Chung, F. and Graham, R. (1998) Erdős on Graphs: His Legacy of Unsolved Problems, A. K. Peters.Google Scholar
[2] Erdős, P. (1997) Some recent problems and results in graph theory. Discrete Math. 164 81–85.Google Scholar
[3] Erdős, P., Faudree, R. J. and Rousseau, C. C. (1992) Extremal problems involving vertices and edges on odd cycles. Discrete Math. 101 23–31.Google Scholar
[4] Füredi, Z. and Maleki, Z. (2014) The minimum number of triangular edges and a symmetrization for multiple graphs. arXiv:1411.0771 Google Scholar
[5] Füredi, Z. and Maleki, Z. A proof and a counterexample for a conjecture of Erdős concerning the minimum number of edges in odd cycles. Manuscript.Google Scholar
[6] Gruslys, V. and Letzter, S. (2016) Minimising the number of triangular edges. arXiv:1605.00528 Google Scholar
[7] Grzesik, A., Hu, P. and Volec, J. (2016) Minimum number of edges that occur in odd cycles. Manuscript.Google Scholar
[8] Motzkin, T. S. and Straus, E. G. (1965) Maxima for graphs and a new proof of a theorem of Turán. Canad. J. Math. 17 533–540.Google Scholar
[9] Turán, P. (1941) On an extremal problem in graph theory (in Hungarian). Matematikai és Fizikai Lapok 48 436–452.Google Scholar
[10] Zykov, A. A. (1949) On some properties of linear complexes (in Russian). Mat. Sbornik (NS) 24 163–188.Google Scholar