Minimizing the number of triangular edges

DOI10.1017/S0963548317000189MaRDI QIDQ3177363zbMATH OpenOpenAlexFDO

Authors Shoham Letzter, Vytautas Gruslys

Publication date 24 July 2018

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.00528

zbMATH Keywords

Zykov's symmetrization method

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Abstract: We consider the problem of minimising the number of edges that are contained in triangles, among $n$-vertex graphs with a given number of edges. We prove a conjecture of F"uredi and Maleki that gives an exact formula for this minimum, for sufficiently large $n$.

Recommendations

• The Minimum Number of Triangular Edges and a Symmetrization Method for Multiple Graphs
• The minimum number of triangles in graphs of given order and size
• Asymptotic structure of graphs with the minimum number of triangles
• On a problem of Erdős and Rothschild on edges in triangles
• The exact minimum number of triangles in graphs with given order and size

Cites work

• Extremal problems involving vertices and edges on odd cycles
• scientific article; zbMATH DE number 3821782 (Why is no real title available?)
• scientific article; zbMATH DE number 3529891 (Why is no real title available?)
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Minimum number of edges that occur in odd cycles
• On a theorem of Rademacher-Turán
• On the Minimal Density of Triangles in Graphs
• The Minimum Number of Triangular Edges and a Symmetrization Method for Multiple Graphs

Cited in

(10)

• The minimum number of triangles in graphs of given order and size
• Edges not in any monochromatic copy of a fixed graph
• Using shortcut edges to maximize the number of triangles in graphs
• Frustrated triangles
• On maximal and minimal triangular planar graphs: an optimization approach
• A polynomial-time algorithm to determine (almost) Hamiltonicity of dense regular graphs
• Asymptotic structure of graphs with the minimum number of triangles
• The Minimum Number of Triangular Edges and a Symmetrization Method for Multiple Graphs
• A spectral Erdős-Faudree-Rousseau theorem
• Spectral supersaturation: triangles and bowties

This page was built for publication: Minimizing the number of triangular edges

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177363)