The maximum number of triangles in F_k-free graphs

2022/07/20 by Zhu, Xiutao, Chen, Yaojun, Gerbner, Dániel +2 · 4 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.2207.10162

Abstract

The generalized Turán number ex(n,K_s,H) is the maximum number of complete graph K_s in an H-free graph on n vertices. Let F_k be the friendship graph consisting of k triangles. Erdős and Sós (1976) determined the value of ex(n,K₃,F₂). Alon and Shikhelman (2016) proved that ex(n,K₃, F_k)≤ (9k-15)(k+1)n. In this paper, by using a method developed by Chung and Frankl in hypergraph theory, we determine the exact value of ex(n,K₃,F_k) and the extremal graph for any F_k when n≥ 4k³.

Cited by

• Anti-Ramsey Number of Stars in 3-uniform hypergraphs
• The generalized Turán number for K₃ in graphs without suspensions of a path on five vertices
• Generalized Turán results for disjoint copies of degenerate graphs
• Generalized Turan number with given size

Related

• The maximum number of triangles in K_1,s,t-free graphs
• On the extremal graphs in generalized Turán problems
• Planar Turán Number of intersecting triangles
• Extremal numbers of disjoint triangles in r-partite graphs
• Survey of generalized Turán problems -- counting subgraphs