Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-17T08:21:44.738Z 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: [email protected], [email protected])
SHOHAM LETZTER
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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