2012/02/02 by Béla Bollobás, BÉLA BOLLOBÁS, Vladimir Nikiforov +1 · 3 citations
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Graph theory and applications
paper · doi:10.1017/s0963548311000654
Let 1 ≤ p ≤ r + 1, with r ≥ 2 an integer, and let G be a graph of order n . Let d ( v ) denote the degree of a vertex v ∈ V ( G ). We show that if then G has more than ( r + 1)-cliques sharing a common edge. From this we deduce that if then G contains more than cliques of order r + 1. In turn, this statement is used to strengthen the Erdős–Stone theorem by using ∑ v ∈ V ( G ) d p ( v ) instead of the number of edges.