Graphs

Graphs may be directed or undirected. In addition, their vertices and/or their edges may be labelled. A graph may be representated by means of its adjacency matrix. or by means of its adjacency list.

• Directed and undirected graphs
• Optional vertex and edge labels
• Operations: union, join, product, contraction, switching etc
• Standard graphs: complete, complete bipartite, k-cube
• Properties: connected, regular, eulerian
• Algebraic invariants: Characteristic polynomial, spectrum
• Diameter, girth, circumference
• Connectedness, paths and circuits
• Spanning trees, cut-vertices
• Cliques and maximal cliques, independent sets
• Chromatic number, chromatic index, chromatic polynomial
• Planarity testing, obstruction isolation, faces, embedding
• Graphs from groups: Cayley graph, orbital graph
• Automorphism group (B. McKay's algorithm), canonical labelling
• Testing of pairs of graphs for isomorphism
• Group actions on a graph: orbits and stabilizers of vertex and edge sequences
• Symmetry properties: vertex transitive, edge transitive, k-arc transitive, distance transitive, distance regular
• Intersection numbers of a distance regular graph
• Interface for B. McKay's graph generation algorithm [15]

Brendan McKay's automorphism program nauty [16] is used for computing automorphism groups and for testing pairs of graphs for isomorphism. In accordance with the Magma philosophy, a graph may be studied under the action of an automorphism group. Using the G-set mechanism an automorphism group can be made to act on any desired set of objects derived from the graph.

The planarity tester and obstruction isolator are linear time algorithms; they are due to Boyer and Myrvold [1].