Upper bound for number of independent sets

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

• Upper bound in terms of what parameters of the graph? – David Richerby Nov 28 '14 at 9:44
• @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. – András Salamon 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.

• 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)$? – 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