The maximum number of cliques in a graph embedded in a surface

Details The maximum number of cliques in a graph embedded in a surface The maximum number of cliques in a graph embedded in a surface

2009-06-22

arxiv.org/abs/0906.4142v3

European J. Combinatorics 32.8:1244-1252, 2011

Mathematics

Combinatorics

Scientific paper

10.1016/j.ejc.2011.04.001

This paper studies the following question: Given a surface $\Sigma$ and an integer $n$, what is the maximum number of cliques in an $n$-vertex graph embeddable in $\Sigma$? We characterise the extremal graphs for this question, and prove that the answer is between $8(n-\omega)+2^{\omega}$ and $8n+{3/2} 2^{\omega}+o(2^{\omega})$, where $\omega$ is the maximum integer such that the complete graph $K_\omega$ embeds in $\Sigma$. For the surfaces $\mathbb{S}_0$, $\mathbb{S}_1$, $\mathbb{S}_2$, $\mathbb{N}_1$, $\mathbb{N}_2$, $\mathbb{N}_3$ and $\mathbb{N}_4$ we establish an exact answer.

Affiliated with

Also associated with

No associations

Rating

The maximum number of cliques in a graph embedded in a surface does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The maximum number of cliques in a graph embedded in a surface, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The maximum number of cliques in a graph embedded in a surface will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-707810