ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 18 Feb 2015 01:46:08 -0600Generating all non-isomorphic bipartite graphs of certain partitionshttp://ask.sagemath.org/question/25864/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!Tue, 17 Feb 2015 21:04:45 -0600http://ask.sagemath.org/question/25864/generating-all-non-isomorphic-bipartite-graphs-of-certain-partitions/Answer by Nathann for <p>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.</p>
<p>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$. </p>
<p>That's it. How could I find all non-isomorphic bipartite graphs with bi-partitions of sizes $n$ and $m$ respectively?</p>
<p>Thank you!</p>
http://ask.sagemath.org/question/25864/generating-all-non-isomorphic-bipartite-graphs-of-certain-partitions/?answer=25865#post-id-25865Nauty 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/graphs/sage/graphs/hypergraph_generators.html
[2] http://www.sagemath.org/doc/reference/graphs/sage/combinat/designs/incidence_structures.html#sage.combinat.designs.incidence_structures.IncidenceStructure.incidence_graphWed, 18 Feb 2015 01:46:08 -0600http://ask.sagemath.org/question/25864/generating-all-non-isomorphic-bipartite-graphs-of-certain-partitions/?answer=25865#post-id-25865