The maximum number of triangles in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" id="d1e97" altimg="si12.svg"><mml:msub><mml:mrow><mml:mi>F</mml:mi></mml:mrow><mml:mrow><mml:mi>k</mml:mi></mml:mrow></mml:msub></mml:math>-free graphs
Xiutao Zhu, Yaojun Chen, Dániel Gerbner, Ervin Győri, Hilal Hama Karim
Abstract
The generalized Turán number ex(n,Ks,H) is the maximum number of complete graph Ks in an H-free graph on n vertices. Let Fk be the friendship graph consisting of k triangles. Erdős and Sós (1976) determined the value of ex(n,K3,F2). Alon and Shikhelman (2016) proved that ex(n,K3,Fk)≤(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,K3,Fk) and the extremal graph for any Fk when n≥4k3.
Topics & Concepts
CombinatoricsMathematicsGraphHypergraphDiscrete mathematicsLimits and Structures in Graph TheoryAdvanced Graph Theory ResearchGraph theory and applications