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.

  • 2
    $\begingroup$ Pick a connected spanning tree of your labeled graph. It has N edges, and your graph has about 10N edges. This alone suggests at least 500^N connected subgraphs which contain this tree. I would not attempt brute force for N greater than 22. $\endgroup$ Jan 31, 2014 at 23:38
  • $\begingroup$ Would you know, by any chance, how many spanning trees are there? $\endgroup$
    – user3487
    Jan 31, 2014 at 23:57
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Kirchhoff's_theorem counts spanning trees. $\endgroup$ Feb 1, 2014 at 2:06


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.