Loading [MathJax]/jax/output/HTML-CSS/jax.js

First time here? Check out the FAQ!

Ask Your Question
2

Generating all non-isomorphic bipartite graphs of certain partitions

asked 10 years ago

chowching gravatar image

updated 9 years ago

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!

Preview: (hide)

1 Answer

Sort by » oldest newest most voted
2

answered 10 years ago

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] http://www.sagemath.org/doc/reference... [2] http://www.sagemath.org/doc/reference...

Preview: (hide)
link

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

Stats

Asked: 10 years ago

Seen: 1,163 times

Last updated: Feb 18 '15