Number of Vertex Covers: when it is polynomial and when it is superpolynomial

Question

The number $C$ of vertex covers of a graph $G = (V, E)$ can be either polynomial in $|V|$ or superpolynomial in $|V|$. $C$ being superpolynomial in $|V|$ doesn't necessarily mean that $C$ is hard to determine. For instance, consider the graph $G = (V, E)$ where $|V| = 2n$ and $E$ is defined as $E = \{ \{ i,j \} | i \mod 2 = 1 \land j = i + 1 \}$: such graph has a number of vertex covers $C=3^{|E|} = 3^{\frac{|V|}{2}}$ which is both superpolynomial in $|V|$ and very easy to determine. On the other hand, knowing in advance that $C$ is polynomial in $|V|$ allows us to use brute force keeping the running time polynomial in $|V|$. So it seems that determing $C$ is hard only if it is superpolynomial in $|V|$, but not always (as the above example demonstrates).

Questions

1. Is it possible to determine in advance if $C$ is polynomial in $|V|$ or superpolynomial in $|V|$? Is there any known result linking some parameter of the graph with the number of its vertex covers? An example of such result would be: "Every graph with $\frac{|E|}{|V|} \geq 4$ has not more than $n^{\frac{|E|}{|V|}}$ vertex covers". Another example would be: "Every graph with $\frac{|E|}{|V|} < 2$ has not less than $1.18^{\sqrt{|E|}}$ vertex covers". How $C$ varies with $G$? Clearly, the more edges $G$ has, the less vertex covers it has: did anyone formalized this trivial fact, showing precisely how $C$ decreases as $|E|$ increases? Which other parameters affect $C$, and how? I mean, from a pure empirical point of view, it's almost evident that a graph with $\frac{|E|}{|V|} \geq 5$ has not so many vertex covers, where "not so many" means "certainly polynomial in $|V|$".
2. When $C$ is superpolynomial in $|V|$ brute force is useless. However, I wonder if, as in the above example, it is always true that $C$ being superpolynomial intrinsically implies the presence of "multiplying blocks" (I don't know how to state this more formally), which in turns would mean that the set of all vertex covers is easy to represent (in other words, it is compactly representable). Is there any known result in this spirit?

Answer 1

There's a close relation between the independence number of a graph and the number of its vertex covers, not close enough to completely answer your question but close: if the independence number is superlogarithmic then the number of covers is superpolynomial, and otherwise it's quasipolynomial.

More specifically if the independence number is $\alpha$, and the maximum independent set $I$ is the complement of a vertex cover $C$, then each of the $2^\alpha$ supersets of $C$ is also a vertex cover. So in this case if $\alpha \ge c\,\log_2 n$ then the number of covers is lower bounded by $n^c$. But each cover is complementary to an independent set and there can be only $O(n^\alpha)$ sets of at most $\alpha$ vertices, so if $\alpha \le c\,\log_2 n$ then this upper bound is $O(2^{c\, \log^2 n})$.