cgraph-theorysage

Generate all non-isomorphic non-bipartite connected graphs of order n


I know that nauty can generate n-vertex bipartite graphs (!geng n -c -b), but I haven't seen a corresponding command for its opposite (non-bipartite graphs). (I might have missed it.)

SageMath provides a way to filter graphs as follows:

 s=[g for g in graphs.nauty_geng('-c 6') if g.is_bipartite()==False]
 len(s)

95

But I would like to ask if there is a closer approach to nauty, such as using a C version to obtain non-bipartite connected graphs. That's because nauty is implemented in C. Alternatively, is there a direct algorithm for generating non-bipartite graphs?


Solution

  • When I asked Brendan McKay, he told me this can works.

    pickg -~b
    

    Besides, pickg can do many things.

                  Constraints:
    
                  Numerical constraints (shown here with following  #)  can  take  a  single  integer
                  value,  or  a  range  like #:#, #:, or :#.  Each can also be preceded by '~', which
                  negates it.   (For example, -~D2:4 will match any maximum degree which is _not_  2,
                  3,  or 4.)  Constraints are applied to all input graphs, and only those which match
                  all constraints are counted or selected.
    
           -n#    number of vertices     -e#  number of edges
    
           -d#    minimum degree         -D#  maximum degree
    
           -m#    vertices of min degree -M#  vertices of max degree
    
           -r     regular                -b   bipartite
    
           -z#    radius                 -Z#  diameter
    
           -g#    girth (0=acyclic)      -Y#  total number of cycles
    
           -T#    number of triangles    -K#  number of maximal independent sets
    
           -H#    number of induced cycles
    
           -E     Eulerian (all degrees are even, connectivity not required)
    
           -a#    group size  -o# orbits  -F# fixed points  -t vertex-transitive
    
           -c#    connectivity (only implemented for 0,1,2).
    
           -i#    min common nbrs of adjacent vertices;     -I# maximum
    
           -j#    min common nbrs of non-adjacent vertices; -J# maximum