Skip to main content
MathOverflow

Return to Question

edit latex
Source Link
edit approved Nov 7, 2016 at 12:37
MR_BD
edit approved Nov 7, 2016 at 12:37
MR_BD
  • 550
  • 5
  • 18

Number of spanning subgraphs of the complete bipartite graph K$K(m,n)$

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

My question is; How many nonisomorphic spanning subgraphs are there of of K(m,n)$K(m,n)$? This is such an obvious question, it has probably been answered. I just don't know wheretowhere 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)$K(m-1,n)$ -- or of Km,n-1)$K(m,n-1)$ -- appending the n-1$n-1$ edges from the missing vertex in the first case or m-1$m-1$ in the second edges in all inequivalent ways will generate the set for K(m,n)$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?

Number of spanning subgraphs of the complete bipartite graph K(m,n)

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?

Number of spanning subgraphs of the complete bipartite graph $K(m,n)$

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?

Source Link
Gustavus Simmons
Gustavus Simmons
  • 63
  • 1
  • 3

Number of spanning subgraphs of the complete bipartite graph K(m,n)

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?