# Generating all non-isomorphic bipartite graphs of certain partitions

Hi everyone. I'm new here and I'm also new in using Sage. I hope someone here could help with what I am trying to do.

I would like to generate all non-isomorphic bipartite graphs given certain partitions. In other words, if $K_{(m,n)}$ is the complete bipartite graph with $m$ and $n$ being the number of vertices in each of its partitions, then what I would like to find is all the spanning subgraphs of $K_{(m,n)}$. These graphs would be bipartite and can be partitioned into two sets with one set having $m$ elements while the other have $n$.

That's it. How could I find all non-isomorphic bipartite graphs with bi-partitions of sizes $n$ and $m$ respectively?

Thank you!

edit retag close merge delete

Sort by » oldest newest most voted

Nauty contains a program to let you enumerate such things (it is called nauty-genbg) but in Sage this feature is exposed through the method "hypergraphs.nauty" [1], which enumerates all hypergraph with a given number of vertices/edges. You can then obtain your bipartite graphs from a hypergraph H by calling H.incidence_graph [2].

more