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

DOI10.1017/S0963548316000407MaRDI QIDQ5366960zbMATH OpenOpenAlexFDO

Authors Zeinab Maleki, Zoltán Füredi

Publication date 10 October 2017

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

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

zbMATH Keywords

Zykov's symmetrization method

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Extremal problems in graph theory (05C35) Extremal combinatorics (05D99)

Abstract: We give an asymptotic formula for the minimum number of edges contained in triangles in a graph having n vertices and e edges. Our main tool is a generalization of Zykov's symmetrization method that can be applied for several graphs simultaneously.

Recommendations

• The minimum number of triangles covering the edges of a graph
• Asymptotic structure of graphs with the minimum number of triangles
• The minimum number of triangles in graphs of given order and size
• scientific article; zbMATH DE number 1305094
• The exact minimum number of triangles in graphs with given order and size
• Minimal triangulations of graphs: a survey
• Minimizing the number of triangular edges
• Using shortcut edges to maximize the number of triangles in graphs
• The minimal density of triangles in tripartite graphs
• On the Minimal Density of Triangles in Graphs

Cites work

• Extremal problems involving vertices and edges on odd cycles
• scientific article; zbMATH DE number 1131467 (Why is no real title available?)
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Minimizing the number of triangular edges
• Minimum number of edges that occur in odd cycles
• Some recent problems and results in graph theory
• The Minimum Number of Triangular Edges and a Symmetrization Method for Multiple Graphs

Cited in

(9)

• Edges not in any monochromatic copy of a fixed graph
• Minimum number of edges that occur in odd cycles
• Minimizing the number of triangular edges
• Asymptotic structure of graphs with the minimum number of triangles
• The Minimum Number of Triangular Edges and a Symmetrization Method for Multiple Graphs
• Refinement on Spectral Turán’s Theorem
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• A spectral Erdős-Faudree-Rousseau theorem
• Spectral supersaturation: triangles and bowties

This page was built for publication: The Minimum Number of Triangular Edges and a Symmetrization Method for Multiple Graphs

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