6
$\begingroup$

Let $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 where to 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 $K(m,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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Austin Mohr
    Commented Feb 15, 2013 at 2:11

1 Answer 1

Reset to default
5
$\begingroup$

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

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

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ira Gessel
    Commented Jun 4, 2012 at 15:12
  • $\begingroup$ 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). $\endgroup$
    – Ira Gessel
    Commented Jun 4, 2012 at 15:15
  • $\begingroup$ Thanks Ira. I will get the two references you cite, but it appears they addess the question I posed. $\endgroup$
    – Gustavus Simmons
    Commented Jun 5, 2012 at 2:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .