Let $G = (V, E)$ be a connected undirected graph. I am interesting in counting the number of connected spanning subgraphs having:
- $\ge 1$ cycle each (but can have any number of cycles),
- Exactly $k \ge 1$ cycles each.
The subgraphs that have $k=1$ are called unicyclic subgraphs. So essentially, I want to count the number of unicyclic spanning subgraphs.
For the first case, it seems that we can just count the number of connected subgraphs (which seems to be #P-complete), then use Kirchhoff's matrix tree theorem to find the number of spanning trees, and find the difference of the two to get the number of connected subgraphs with $\ge 1$ cycle each.
The second problem seems like a special case of the first, but I haven't been able to find any resources of its complexity. I'm not even sure how to do this for a fixed value of $k$.
The application of this would be on better approximating coefficients of the reliability polynomial.
Edit: another interesting direction would be to investigate $k$-regular graphs for $k \ge 3$ (the $k=2$ case is known, of course).
Edit 2: for planar graphs, counting unicyclic subgraphs is poly-time computable (and due to Myrvold, this is reducible to matrix multiplication): http://link.springer.com/article/10.1007%2FBF01994058