Number of cliques in a graph

I think the number of cliques in a graph is generally exponential in the of vertices of that graph. Does anyone know any reference for that?

I am assuming you mean the number of maximal cliques, as the number of cliques of a complete graph is trivially $2^n$ (any subset of the vertices forms a clique).

For the number of maximal cliques, take the complement of a disjoint union of triangles. Since the number of maximal independent sets is exactly the same (in the complement), you can count the number of maximal independent set in a graph that is a disjoint union of triangles. This number is $3^{n/3}$ (Moon and Moser, 1965).

See also: The number of cliques in a graph: the Moon and Moser 1965 result.

StackExchange Computer Science Q#79294, answer score: 5