Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6424408 | European Journal of Combinatorics | 2011 | 9 Pages |
Abstract
This paper studies the following question: given a surface Σ and an integer n, what is the maximum number of cliques in an n-vertex graph embeddable in Σ? We characterise the extremal graphs for this question, and prove that the answer is between 8(nâÏ)+2Ï and 8n+522Ï+o(2Ï), where Ï is the maximum integer such that the complete graph KÏ embeds in Σ. For the surfaces S0, S1, S2, N1, N2, N3 and N4 we establish an exact answer.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Vida DujmoviÄ, GaÅ¡per Fijavž, Gwenaël Joret, Thom Sulanke, David R. Wood,