next | previous | forward | backward | up | top | index | toc | Macaulay2 website
Nauty :: generateBipartiteGraphs

generateBipartiteGraphs -- generates the bipartite graphs with a given bipartition

Synopsis

Description

This method generates all bipartite graphs on $n$ vertices. The size of the bipartition is specified by giving the size of one class; the other class is determined automatically from the number of vertices.

If only one integer argument is given, then the method generates all bipartite graphs on that number of vertices with first class of sizes $0$ to $n$.

If a PolynomialRing $R$ is supplied instead, then the number of vertices is the number of generators. Moreover, the strings are automatically converted to graphs in $R$.

i1 : R = QQ[a..e];
i2 : generateBipartiteGraphs(R, 2)

o2 = {Graph{edges => {}                }, Graph{edges => {{a, e}}          },
            ring => R                           ring => R                    
            vertices => {a, b, c, d, e}         vertices => {a, b, c, d, e}  
     ------------------------------------------------------------------------
     Graph{edges => {{a, e}, {b, e}}  }, Graph{edges => {{a, d}, {a, e}}  },
           ring => R                           ring => R                    
           vertices => {a, b, c, d, e}         vertices => {a, b, c, d, e}  
     ------------------------------------------------------------------------
     Graph{edges => {{a, d}, {b, e}}  }, Graph{edges => {{a, d}, {a, e}, {b,
           ring => R                           ring => R                    
           vertices => {a, b, c, d, e}         vertices => {a, b, c, d, e}  
     ------------------------------------------------------------------------
     e}}}, Graph{edges => {{a, d}, {b, d}, {a, e}, {b, e}}},
                 ring => R                                  
                 vertices => {a, b, c, d, e}                
     ------------------------------------------------------------------------
     Graph{edges => {{a, c}, {a, d}, {a, e}}}, Graph{edges => {{a, c}, {a,
           ring => R                                 ring => R            
           vertices => {a, b, c, d, e}               vertices => {a, b, c,
     ------------------------------------------------------------------------
     d}, {a, e}, {b, e}}}, Graph{edges => {{a, c}, {b, d}, {a, e}}},
                                 ring => R                          
     d, e}                       vertices => {a, b, c, d, e}        
     ------------------------------------------------------------------------
     Graph{edges => {{a, c}, {b, d}, {a, e}, {b, e}}},
           ring => R                                  
           vertices => {a, b, c, d, e}                
     ------------------------------------------------------------------------
     Graph{edges => {{a, c}, {a, d}, {b, d}, {a, e}, {b, e}}},
           ring => R                                          
           vertices => {a, b, c, d, e}                        
     ------------------------------------------------------------------------
     Graph{edges => {{a, c}, {b, c}, {a, d}, {b, d}, {a, e}, {b, e}}}}
           ring => R
           vertices => {a, b, c, d, e}

o2 : List

Caveat

The number of vertices $n$ must be positive as nauty cannot handle graphs with zero vertices.

See also

Ways to use generateBipartiteGraphs :

For the programmer

The object generateBipartiteGraphs is a method function with options.