The maximum number of cliques in dense graphs

✍ Scribed by Bruce Hedman

• Publisher: Elsevier Science
• Year: 1985
• Tongue: English
• Weight: 372 KB
• Volume: 54
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(85)90077-9

✦ Synopsis

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 concerned only with undirected, connected graphs without loops or multiple edges. For terms not explicitly defined below we will follow Harary [5]. If u and v are vertices of G denote the edge between them by uv. A clique of graph G is a maximal complete subgraph of G. The clique graph K(G) of a graph G is the intersection graph of the cliques of G. The clique graph of K(G) will be written K2(G). Denote the number of vertices of a graph G by ]G]. The induced subgraph (S) on a subset S of the vertices of G is the graph with vertices S and s~s i ~ e((S)) if and only if s~sj ~ e(G). The density o(G) of graph G is the number of vertices in the largest clique of G. A graph G will be called dense if oJ(G)>~½ ]G[. For v ~ v(G) let F(v) = {u ~ v(G): vu~ e(G)}.