Graphs [HB 93]

Changes:

• The nauty program (B. McKay) has been updated to version 2.0. Version 2.0 has a larger range of invariants to work with when trying to refine a graph's partition, thus considerably speeding up the search for a canonical labelling of difficult graphs. The available invariants and their respective use are fully documented in the Magma handbook.

  In addition, Version 2.0 now uses dynamic memory allocation which allows nauty to work on graphs on any size.

• In addition to AutomorphismGroup, the functions IsDistanceTransitive, IsEdgeTransitive, IsTransitive, IsPrimitive, IsSymmetric, EdgeGroup, OrbitsPartition, IsIsomorphic, and CanonicalGraph now allow users to set a parameter suite given them more control over which automorphism group to compute.

New Features:

• A function TestNautyInvariant is provided to help the user decide which invariant is to be used to run nauty.
• The function StronglyRegularGraphsDatabase gives access to a catalogue of strongly regular graphs due to B. McKay et al. Standard access functions to help retrieve the graphs in the catalogue are also provided.

  The function GenerateGraphs gives access to the graph generation program written by B. McKay. This feature is only available on Unix platforms as graphs are generated (and read from) within a Unix pipe.

  The graph generation program allows users to generate any isomorph-free collection of graphs responding to several criteria like, among others, the connectedness of the graphs, or whether they are 3 or 4-cycle free.

• The function OpenGraphFile enables the user to open any file of graphs or any graph generating pipe. The graphs must be in a specified format, and the pipe mechanism is only available on Unix platforms. The function NextGraph is used to read any graph in the stream output from GenerateGraphs or OpenGraphFile.