Ask Your Question

Generating all non-isomorphic bipartite graphs of certain partitions

asked 2015-02-18 04:04:45 +0200

chowching gravatar image

updated 2015-07-31 17:55:01 +0200

FrédéricC gravatar image

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 flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted

answered 2015-02-18 08:46:08 +0200

Nathann gravatar image

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].

[1] [2]

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2015-02-18 04:04:45 +0200

Seen: 1,045 times

Last updated: Feb 18 '15