On the maximum number of cliques in a graph embedded in a surface

Publication date 29 November 2011

Abstract: This paper studies the following question: Given a surface

S i g m a

and an integer

n

, what is the maximum number of cliques in an

n

-vertex graph embeddable in

S i g m a

? We characterise the extremal graphs for this question, and prove that the answer is between

8 (n - o m e g a) + 2^{o m e g a}

and

8 n + 3 / 2 2^{o m e g a} + o (2^{o m e g a})

, where

o m e g a

is the maximum integer such that the complete graph

K_{o} m e g a

embeds in

S i g m a

. For the surfaces

m a t h b b S_{0}

,

m a t h b b S_{1}

,

m a t h b b S_{2}

,

m a t h b b N_{1}

,

m a t h b b N_{2}

,

m a t h b b N_{3}

and

m a t h b b N_{4}

we establish an exact answer.

Recommendations

Cites work

Cited in

(10)

This page was built for publication: On the maximum number of cliques in a graph embedded in a surface