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$ – The Masked Avenger Jan 31 '14 at 23:38
  • $\begingroup$ Would you know, by any chance, how many spanning trees are there? $\endgroup$ – user3487 Jan 31 '14 at 23:57
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Kirchhoff's_theorem counts spanning trees. $\endgroup$ – Benjamin Young Feb 1 '14 at 2:06

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.