Large joints in graphs

DOI10.1016/J.EJC.2010.07.010zbMATH Open1202.05066OpenAlexW1977378525MaRDI QIDQ607362FDOQ607362

Authors Béla Bollobás, Vladimir Nikiforov

Publication date 22 November 2010

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

number of cliquesTuran r-partite graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: We show that if G is a graph of sufficiently large order n containing as many r-cliques as the r-partite Turan graph of order n; then for some C>0 G has more than Cn^(r-1) (r+1)-cliques sharing a common edge unless G is isomorphic to the the r-partite Turan graph of order n. This structural result generalizes a previous result that has been useful in extremal graph theory.

Recommendations

• Joints in graphs
• Graphs with many r -cliques have large complete r -partite subgraphs
• On the number of edge disjoint cliques in graphs of given size
• An extension of Turán's theorem, uniqueness and stability
• The typical structure of graphs with no large cliques

Cites work

• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 3745218 (Why is no real title available?)
• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 3258858 (Why is no real title available?)
• scientific article; zbMATH DE number 3185004 (Why is no real title available?)
• scientific article; zbMATH DE number 3050594 (Why is no real title available?)
• Books in graphs
• Extremal graphs for intersecting triangles
• Joints in graphs
• On a theorem of Rademacher-Turán
• On complete subgraphs of different orders
• On the number of complete subgraphs and circuits contained in graphs
• Ramsey goodness and beyond
• Stability for large forbidden subgraphs
• Turán's theorem inverted

Cited in

(6)

• scientific article; zbMATH DE number 2138155 (Why is no real title available?)
• Short proofs of some extremal results. III
• Another extremal problem for Turan graphs
• Graphs with many r -cliques have large complete r -partite subgraphs
• Spectral saturation: inverting the spectral Turán theorem
• Joints in graphs

This page was built for publication: Large joints in graphs

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