generateGraphs -- generates the graphs on a given number of vertices

Synopsis

Usage:

G = generateGraphs n

G = generateGraphs(n, e)

G = generateGraphs(n, le, ue)

G = generateGraphs R

G = generateGraphs(R, e)

G = generateGraphs(R, le, ue)
Inputs:
- R, a polynomial ring, the ring in which the graphs will be created
- n, an integer, the number of vertices of the graphs, must be positive (see caveat)
- e, an integer, the number of edges in the graphs
- le, an integer, a lower bound on the number of edges in the graphs
- ue, an integer, an upper bound on the number of edges in the graphs
Optional inputs:
- MaxDegree => an integer, default value null, an upper bound on the degrees of the vertices
- MinDegree => an integer, default value null, a lower bound on the degrees of the vertices
- Only4CycleFree => a Boolean value, default value false, whether to only allow graphs without 4-cycles
- OnlyBiconnected => a Boolean value, default value false, whether to only allow biconnected graphs
- OnlyBipartite => a Boolean value, default value false, whether to only allow bipartite graphs
- OnlyConnected => a Boolean value, default value false, whether to only allow connected graphs
- OnlyTriangleFree => a Boolean value, default value false, whether to only allow graphs without triangles (3-cycles)
Outputs:
- G, a list, the graphs satisfying the input conditions

Description

This method generates all graphs on $n$ vertices subject to the constraints on the number of edges. It uses numerous options to allow further constraining of the output.

If a PolynomialRing $R$ is supplied instead, then the number of vertices is the number of generators. Moreover, the nauty-derived strings are automatically converted to instances of the class Graph in $R$.

i1 : R = QQ[a..e];

i2 : generateGraphs(R, 4, 6, OnlyConnected => true)

o2 = {Graph{"edges" => {{a, e}, {b, e}, {c, e}, {d, e}}},
            "ring" => R                                  
            "vertices" => {a, b, c, d, e}                
     ------------------------------------------------------------------------
     Graph{"edges" => {{a, d}, {a, e}, {b, e}, {c, e}}},
           "ring" => R                                  
           "vertices" => {a, b, c, d, e}                
     ------------------------------------------------------------------------
     Graph{"edges" => {{a, d}, {a, e}, {b, e}, {c, e}, {d, e}}},
           "ring" => R                                          
           "vertices" => {a, b, c, d, e}                        
     ------------------------------------------------------------------------
     Graph{"edges" => {{a, d}, {b, d}, {a, e}, {b, e}, {c, e}}},
           "ring" => R                                          
           "vertices" => {a, b, c, d, e}                        
     ------------------------------------------------------------------------
     Graph{"edges" => {{a, d}, {b, d}, {a, e}, {c, e}, {d, e}}},
           "ring" => R                                          
           "vertices" => {a, b, c, d, e}                        
     ------------------------------------------------------------------------
     Graph{"edges" => {{a, d}, {b, d}, {a, e}, {b, e}, {c, e}, {d, e}}},
           "ring" => R                                                  
           "vertices" => {a, b, c, d, e}                                
     ------------------------------------------------------------------------
     Graph{"edges" => {{a, d}, {b, d}, {c, d}, {a, e}, {b, e}, {c, e}}},
           "ring" => R                                                  
           "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}, {b, d}, {a, e}, {b, e}, {c, e}}},
           "ring" => R                                          
           "vertices" => {a, b, c, d, e}                        
     ------------------------------------------------------------------------
     Graph{"edges" => {{a, c}, {b, d}, {a, e}, {b, e}, {c, e}, {d, e}}},
           "ring" => R                                                  
           "vertices" => {a, b, c, d, e}                                
     ------------------------------------------------------------------------
     Graph{"edges" => {{a, c}, {a, d}, {b, d}, {b, e}, {c, e}}},
           "ring" => R                                          
           "vertices" => {a, b, c, d, e}                        
     ------------------------------------------------------------------------
     Graph{"edges" => {{a, c}, {a, d}, {b, d}, {a, e}, {b, e}, {c, e}}},
           "ring" => R                                                  
           "vertices" => {a, b, c, d, e}                                
     ------------------------------------------------------------------------
     Graph{"edges" => {{a, c}, {a, d}, {c, d}, {a, e}, {b, e}, {c, 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.

Ways to use generateGraphs :

generateGraphs(PolynomialRing)
generateGraphs(PolynomialRing,ZZ)
generateGraphs(PolynomialRing,ZZ,ZZ)
generateGraphs(ZZ)
generateGraphs(ZZ,ZZ)
generateGraphs(ZZ,ZZ,ZZ)

For the programmer