𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by Vida Dujmović; Gašper Fijavž; Gwenaël Joret; Thom Sulanke; David R. Wood

Book ID
113582356
Publisher
Elsevier Science
Year
2011
Tongue
English
Weight
266 KB
Volume
32
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The maximum number of cliques in dense g
The maximum number of cliques in dense graphs
✍ Bruce Hedman 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 372 KB

Denote the number of vertices of G by ]G[. A clique of graph G is a maximal complete subgraph. The density oJ(G) is the number of vertices in the largest clique of G. If ¢o(G)>~½ ]GI, then G has at most 2 t°l-'cG) cliques. The extremal graphs are then examined as wen. ## Terminology We will be co

On the maximum number of cycles in a pla
On the maximum number of cycles in a planar graph
✍ R. E. L. Aldred; Carsten Thomassen 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 142 KB 👁 2 views

## Abstract Let __G__ be a graph on __p__ vertices with __q__ edges and let __r__ = __q__ − __p__ = 1. We show that __G__ has at most ${15\over 16} 2^{r}$ cycles. We also show that if __G__ is planar, then __G__ has at most 2^__r__ − 1^ = __o__(2^__r__ − 1^) cycles. The planar result is best possib