Large joints in graphs

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

Authors: Béla Bollobás, Vladimir Nikiforov 

Publication date: 22 November 2010

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Extremal graphs for intersecting triangles
• Title not available (Why is that?)
• Title not available (Why is that?)
• Ramsey goodness and beyond
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Turán's theorem inverted
• Joints in graphs
• On the number of complete subgraphs and circuits contained in graphs
• On complete subgraphs of different orders
• Stability for large forbidden subgraphs
• On a theorem of Rademacher-Turán
• Books in graphs

Cited In (6)

• Short proofs of some extremal results III
• Graphs with many r -cliques have large complete r -partite subgraphs
• Title not available (Why is that?)
• Spectral saturation: inverting the spectral Turán theorem
• Joints in graphs
• Another extremal problem for Turan 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)