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?
4
-
2$\begingroup$ I would recommend reading this: arxiv.org/abs/math/0602191 $\endgroup$– ryanCommented Jul 24, 2017 at 22:32
-
3$\begingroup$ What have you tried? Have you tried counting the number of cliques in the complete graph on $n$ vertices, as a function of $n$? $\endgroup$– D.W. ♦Commented Jul 24, 2017 at 22:48
-
1$\begingroup$ This is an extremely straightforward observation (consider @D.W.'s suggestion) and a citation isn't required. Sure, you could probably find somebody who's published this fact but giving them a citation would look silly and they certainly won't have been the first person to make the observation. $\endgroup$– David RicherbyCommented Jul 24, 2017 at 22:53
-
$\begingroup$ @D.W. Thanks, for a complete graph of $n$ vertices, I think the number of cliques is $n \choose 1$ + $n \choose 2$ + $\ldots$ + $n \choose n$ = $2^n$. Am I right? $\endgroup$– m0_asCommented Jul 25, 2017 at 1:29
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Jul 25, 2017 at 15:46