0
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ I would recommend reading this: arxiv.org/abs/math/0602191 $\endgroup$ – ryan Jul 24 '17 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. Jul 24 '17 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 Richerby Jul 24 '17 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_as Jul 25 '17 at 1:29
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.