Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)?

share|improve this question
1  
Welcome to MSE! Do you have any thoughts on the question that you can share? Regards –  Amzoti Jul 19 '13 at 23:46
add comment

1 Answer 1

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.

share|improve this answer
1  
Moon and Moser in 1965 showed that in general graphs the number of maximal cliques could increase as $3^{n/3}$, please refer to this post: cstheory.stackexchange.com/questions/8390/… But the following paper shows that in graphs with maximum degree $\Delta$, the number of cliques (all, not just maximal) could be exponential in $\Delta$ but increases only linearly with $n$: arxiv.org/abs/math/0602191 We can expect an even sharper bound if we limit to maximal cliques in bounded degree graphs. I'm looking for this bound! –  Chandra Jul 20 '13 at 23:04
    
Moon and Moser's result is on the maximum number of cliques, not the number of maximal cliques. (Notice that $3^{n/3}$ could be a lot larger than $n$.) Are you interested in the number of maximal cliques or the maximal number of cliques? –  hattoriace Jul 21 '13 at 2:08
    
Hattoriace, it is easy to see that complete bipartite graph $K_{\lfloor n/2\rfloor, \lceil n/2 \rceil}$ has $n$ vertices and $\lfloor \frac{n^2}4 \rfloor$ maximal cliques, all of size $2$, so your upper “bound” has no sense. –  Smylic Jan 8 at 0:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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