Article ID Journal Published Year Pages File Type
6424408 European Journal of Combinatorics 2011 9 Pages PDF
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
, , , , ,