| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4654087 | European Journal of Combinatorics | 2011 | 12 Pages |
Abstract
We show that if r≥s≥2,n>r8r≥s≥2,n>r8, and GG is a graph of order nn containing as many rr-cliques as the rr-partite Turán graph of order nn, then GG has more than nr−1/r2r+12nr−1/r2r+12 cliques sharing a common edge unless GG is isomorphic to the rr-partite Turán graph of order nn. This structural result generalizes a previous result that has been useful in extremal graph theory.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Béla Bollobás, Vladimir Nikiforov,