What is the tightest upper bound known for the number of independent sets in a graph?

  • 2
    $\begingroup$ Upper bound in terms of what parameters of the graph? $\endgroup$ Nov 28 '14 at 9:44
  • $\begingroup$ @David: I think this question is worthwhile even without specifying the parameters, since there are only two that are typically considered (vertices and vertices/edges); this is reflected in the answers. $\endgroup$ Nov 29 '14 at 13:34

The trivial upper bound of $2^n$ (on a graph with $n$ vertices) is as tight as you can get, since a graph that has no edges does indeed have $2^n$ independent sets.

  • 6
    $\begingroup$ Is there such a simple bound that takes into account the number $m$ of edges in the graph? If $I(n,m)$ denotes the maximal number of independent sets in a graph with $n$ vertices and $m$ edges, we have $I(n,0)=2^n$, $I(n,n(n-1)/2)=n+1$ and $I(n,1)=3\cdot 2^{n-2}$ (if I made no mistake). Do we have a closed form formula for $I(n,m)$? $\endgroup$
    – Bruno
    Nov 27 '14 at 16:16

If $I(n,m)$ denotes the maximal number of independent sets in a graph with $n$ vertices and $m$ edges.

$I(n,n-1) = 2^{n-1}+1$ is achieved by a star (should be easy to prove, start by proving that any graph with a matching of size $3$ has at most $3^3\times 2^{n-6}$ independent sets, then show that we can not have two node disjoint paths of length $3$ and no induced path of length $4$, the only remaining graph will be the star).

Let $k(n,m)$ be minimum number such that $k(k-1)/2 + k(n-k) > m$. Then there exit graphs with $n$ nodes and $m$ edges having $2^{n-k}+k$ independent sets. Namely an independent set of size n-k and k universal vertices. I think this is close to optimal, hence:

$$I(n,m) \ge 2^{n-k(n,m)}+k(n,m)$$

A more precise bound can be derived from David R. Wood's study of number of cliques,On the Maximum Number of Cliques in a Graph


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.