maximum number of maximal cliques 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)?
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.
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.