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)?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.