We consider only finite, undirected graphs without loops or multiple edges. A clique of a graph G is a maximal complete subgraph of G. The clique number w(G) is the number of vertices in the largest clique of G. This note addresses the foflowing question: Which graphs G on n vertices with w(G) = r have the maximum number of cliques?
Notation
We will consider only finite, undirected graphs without loops or multiple edges. Denote the vertex set and the edge set of G by v(G) and e(G), respectively. Let ISI denote the number of elements in set S. A clique of graph G is a maximal complete subgraph. The clique graph K(G) is the intersection graph of the cliques of G. Let C(G) denote the set of all complete subgraphs of G. The clique number w(G) is the number of vertices in the largest clique of G. For 1 < r < n let F(n) = max{IK(G)l" Iv(G)l = n) G and let
F(n, r)=max{IK(G)l: Iv(G)l =n and re(G)--r).
G Let f(n, r) = max{lC(G)l: Iv(G)l -n and w(G) = r}. G A Turan graph T(n, r) is a multipartite graph constructed in the following way: on n vertices Vx,..., vn connect by an edge vi and vj if and only if i #:j (mod r). Denote IK(T(n, r))[ by tk (n, r) and IC(T(n, r))l by to(n, r). 1. BKiq~und In 1941 P. Turan [5] introduced this multipartite graph T(n, r) as the unique graph which maximizes the number of edges of a graph of n vertices without a