Suppose $G$ is a connected simple labeled graph. Let $n$, $e$, and $k$ be its number of vertices, edges, and the upper bound of the degree of a vertex, respectively. How many connected sub-graphs containing all $n$ vertices does $G$ have? (In other words, how many connected factors $G$ has?) Is there an algorithm that generates all such cases?
For example:
1) the Graph 0--0--0--0--0 has only one such factor.
2) a complete graph has loads of such factors (see Are there more connected or disconnected graphs on $n$ vertices? )
The case I am working on lays somewhere between the above two examples. In my situation, $n$ is large (say 3000) but the graph is sparse in the sense that each vertex has degree at most equal to 20 or 30. Furthermore, I have a notion of distance between points - far away points cannot share an edge. The situation is similar to connecting the cities of a country with roads - there are loads of cities, but each city will have few roads emanating from it, and cities that are far away will not share a direct road. All cities should connected to the transportation grid. How many such grids are there? In other words, I am trying to count the number of $(1,20)$-Factors. I need to know this number to check if the brute force computation I am considering is not feasible.
