maximum number of maximal cliques

$\begingroup$

I would like to know about upper bounds on the number of maximal cliques in graphs with small degrees. More precisely, how does the number of maximal cliques scale with graph size (i.e., number of nodes and links) and maximum degree (maximum of the degrees of all the nodes)?

$\endgroup$ 1

1 Answer

$\begingroup$

If we know the size of the maximal clique $k$ then a trivial upper bound is $n/k$. An upper bound on the number of maximal cliques of all graphs is the number of vertices. An upper bound on the size of maximal clique is the maximum node degree $d$. Suppose $d$ is small relative to $n$, then the number of maximal clique is bounded by $n /d$ from below and $n$ from above.

$\endgroup$ 3

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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