Hostname: page-component-745bb68f8f-d8cs5 Total loading time: 0 Render date: 2025-02-06T17:16:30.365Z Has data issue: false hasContentIssue false
  • English
  • Français

Minimizing the Number of Triangular Edges

Part of: Graph theory

Published online by Cambridge University Press:  14 August 2017

VYTAUTAS GRUSLYS  and
SHOHAM LETZTER
VYTAUTAS GRUSLYS
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: v.gruslys@dpmms.cam.ac.uk, s.letzter@dpmms.cam.ac.uk)
SHOHAM LETZTER
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: v.gruslys@dpmms.cam.ac.uk, s.letzter@dpmms.cam.ac.uk)
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 consider the problem of minimizing the number of edges that are contained in triangles, among n-vertex graphs with a given number of edges. For sufficiently large n, we prove an exact formula for this minimum, which partially resolves a conjecture of Füredi and Maleki.

MSC classification

Primary: 05C35: Extremal problems
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Special Issue 4: Special Issue: Oberwolfach Workshop , July 2018 , pp. 580 - 622
Copyright
Copyright © Cambridge University Press 2017 

References

[1] Erdős, P. (1955) Some theorems on graphs (in Hebrew). Riveon Lematematika 9 13–17.Google Scholar
[2] Erdős, P. (1962) On a theorem of Rademacher–Turán. Illinois J. Math 6 122–127.CrossRefGoogle 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.CrossRefGoogle Scholar
[4] Füredi, Z. and Maleki, Z. (2017) The minimum number of triangular edges and a symmetrization method for multiple graphs. Combin. Probab. Comput. 26 525–535.CrossRefGoogle 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 on odd cycles. Manuscript.Google Scholar
[6] Grzesik, A., Hu, P. and Volec, J. Minimum number of edges that occur in odd cycles. arXiv:1605.09055Google Scholar
[7] Lovász, L. and Simonovits, M. (1976) On the number of complete subgraphs of a graph. In Proc. Fifth British Combinatorial Conference (Aberdeen 1975) (Nash-Williams, C. St. J. A. and Sheehan, J., eds), Utilitas Mathematica, pp. 431–442.Google Scholar
[8] Lovász, L. and Simonovits, M. (1983) On the number of complete subgraphs of a graph II. In Studies in Pure Mathematics: To the Memory of Paul Turán (Erdős, P. et al., eds), Birkhäuser, pp. 459–495.CrossRefGoogle Scholar
[9] Mantel, W. (1907) Problem 28. Wiskundige Opgaven 10 60–61.Google Scholar
[10] 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.CrossRefGoogle Scholar
[11] Rademacher, H. (1941). Unpublished manuscript.Google Scholar
[12] Razborov, A. (2008) On the minimal density of triangles in graphs. Combin. Probab. Comput. 17 603–618.CrossRefGoogle Scholar
[13] Turán, P. (1941) Eine Extremalaufgabe aus der Graphentheorie. Mat. Fiz Lapok 48 436–452.Google Scholar