Trees: complexity of counting the number of vertex covers Which is the complexity of counting the number of vertex covers of trees? Is it still #P-complete, as for general graphs?
The complement of a vertex cover is an independent set.  Your question is therefore equivalent to asking whether counting independent sets is #P-complete on trees.

The answer to this question is NO, it is not #P-complete: there is actually a polynomial-time algorithm to count the number of solutions.


S. D. Noble, Evaluating a Weighted Graph Polynomial for 
Graphs of Bounded Tree-Width, The Electronic Journal of Combinatorics 16(1) R64, 2009. (link)


Noble actually shows much more.  Suppose the class of graphs under consideration has treewidth at most $k$.  Then the weighted graph polynomial $U$, which evaluated at a certain point yields the number of independent sets of a graph, can be evaluated in $O(a_k n^{2k+3})$ operations at any point.  Here $a_k$ depends only on $k$ and $n$ is the number of vertices in the input graph.  Hence there is a polynomial-time algorithm to count the number of vertex covers on trees (or any other class of graphs of bounded treewidth).



On the other side, it is interesting to ask: what is the smallest class that is known to be #P-complete?


  Theorem (Greenhill, 2000): counting independent sets in 3-regular graphs is #P-complete. (link).


In the comments Colin McQuillan pointed out an even stronger result:


Mingji Xia, Wenbo Zhao, #3-Regular Bipartite Planar Vertex Cover is #P-Complete, TAMC 2006, 356–364.


Note that wall graphs are 3-regular (if their corners are joined up), bipartite, and planar, but they have arbitrarily large treewidth.

Finally, a different graph polynomial $R_2$ yields the number of independent sets in a bipartite graph.  This was posed as an open question:


  Question (Ge and Štefankovič, 2010): is the exact evaluation of the $R_2$ polynomial easy for bounded tree-width graphs? (link)