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

I don't know how to type subscripts here, so K(m,n) denotes the complete bipartite graph on parts of cardinality m and n.

My question is; How many nonisomorphic spanning subgraphs are there of of K(m,n)? This is such an obvious question, it has probably been answered. I just don't know whereto look. There is an obvious, but complex to use, recursion for the constructions. Given the set of nonisomorphic subgraphs of K(m-1,n) -- or of Km,n-1) -- appending the n-1 edges from the missing vertex in the first case or m-1 in the second edges in all inequivalent ways will generate the set for K(m,n). But this is not a numerical problem so no simple recursion seems possible -- yet it may have well been solved using Polya's counting theorem. Do any of you know the answer, or where it can be found?

share|improve this question
    
If you are indeed interested in just spanning trees of $K(m,n)$, then you may find more information at www.austinmohr.com/work (under "Master's Thesis"). Moreover, the algorithm used to enumerate the trees should be easy to adapt to counting any sort of subgraph, though the runtime will suffer. There is a polytime algorithm for determining isomorphism between trees, but there is not yet one for general graphs. –  Austin Mohr Feb 15 '13 at 2:11

1 Answer 1

up vote 5 down vote accepted

This is only known explicitly for $m=4$. A decent survey is here:

http://www.math.ru.nl/~bosma/Students/JannekevandenBoomen/JannekevdBoomenMScthesis.pdf

share|improve this answer
1  
This paper is about spanning trees, not spanning graphs. The problem is a variation of the problem of counting unlabeled bipartite graphs and it seems likely that it could be solved using the methods that can be used to count bipartite graphs. See, for example, Frank Harary and Geert Prins, Enumeration of bicolourable graphs, Canad. J. Math. 15 (1963), 237–248 and Phil Hanlon, The enumeration of bipartite graphs, Discrete Math. 28 (1979), 49–57. –  Ira Gessel Jun 4 '12 at 15:12
    
The variation in which we count unlabeled bicolored graphs, i.e, isomorphism classes of graphs with m red and n blue vertices, where every edge connects a blue vertex to a red vertex, and where isomorphisms must preserve the colors of the vertices, is much easier, and can be solved by a straightforward application of Polya's theorem (or Burnside's lemma). –  Ira Gessel Jun 4 '12 at 15:15
    
Thanks Ira. I will get the two references you cite, but it appears they addess the question I posed. –  Gustavus Simmons Jun 5 '12 at 2:18

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.