Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
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. –  The Masked Avenger Jan 31 at 23:38
    
Thanks a lot Avenger. –  user3487 Jan 31 at 23:54
    
Would you know, by any chance, how many spanning trees are there? –  user3487 Jan 31 at 23:57
1  
en.wikipedia.org/wiki/Kirchhoff's_theorem counts spanning trees. –  Benjamin Young Feb 1 at 2:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.