Graphs

• Introduction
• Construction of Graphs and Digraphs
  • Bounds on the Graph Order
    • GraphSizeInBytes(n, m : parameters): RngIntElt, RngIntElt → RngIntElt
    • Example: Grph Size
  • Construction of a General Graph
    • Graph< n | edges : parameters>: RngIntElt, List → GrphUnd, GrphVertSet, GrphEdgeSet
    • Graph< S | edges : parameters >: SetEnum, List → GrphUnd, GrphVertSet, GrphEdgeSet
    • Graph< S | edges : parameters>: SetIndx, List → GrphUnd, GrphVertSet, GrphEdgeSet
    • IncidenceGraph(A): ModMatRngElt → GrphUnd
    • Example: Constructors
    • Example: Tutte Cage
  • Construction of a General Digraph
    • Digraph< n | edges : parameters>: RngIntElt, List → GrphDir
    • Digraph< S | edges : parameters>: SetEnum, List → GrphDir
    • Digraph< S | edges : parameters>: SetIndx, List → GrphDir
    • IncidenceDigraph(A): ModMatRngElt → GrphDir
    • Example: Constructors
  • Operations on the Support
    • Support(G): Grph → SetIndx
    • Support(V): GrphVertSet → SetIndx
    • ChangeSupport(G, S): Grph, SetIndx → Grph, GrphVertSet, GrphEdgeSet
    • ChangeSupport(~G, S): Grph, SetIndx
    • StandardGraph(G): Grph → Grph
    • Example: Constructors
  • Construction of a Standard Graph
    • BipartiteGraph(m, n): RngIntElt, RngIntElt → GrphUnd
    • CompleteGraph(n): RngIntElt → GrphUnd
    • KCubeGraph(n : parameters): RngIntElt → GrphUnd
    • MultipartiteGraph(Q): [RngIntElt] → GrphUnd
    • EmptyGraph(n : parameters): RngIntElt → GrphUnd
    • NullGraph( : parameters) → GrphUnd
    • PathGraph(n : parameters): RngIntElt → GrphUnd
    • PolygonGraph(n : parameters): RngIntElt → GrphUnd
    • RandomGraph(n, r : parameters): RngIntElt, FldReElt → GrphUnd
    • RandomTree(n : parameters): RngIntElt → GrphUnd
  • Construction of a Standard Digraph
    • CompleteDigraph(n): RngIntElt → GrphDir
    • EmptyDigraph(n : parameters): RngIntElt → GrphDir
    • RandomDigraph(n, r : parameters): RngIntElt, FldReElt → GrphDir
    • Example: Constructors
• Graphs with a Sparse Representation
  • HasSparseRep(G): Grph → BoolElt
  • HasDenseRep(G): Grph → BoolElt
  • HasSparseRepOnly(G): Grph → BoolElt
  • HasDenseRepOnly(G): Grph → BoolElt
  • HasDenseAndSparseRep(G): Grph → BoolElt
  • Example: Sparse Reps
• The Vertex–Set and Edge–Set of a Graph
  • Introduction
  • Creating Edges and Vertices
    • EdgeSet(G): Grph → GrphEdgeSet
    • Edges(G): Grph → { @ GrphEdge @ }
    • VertexSet(G): Grph → GrphVertSet
    • Vertices(G): Grph → { GrphVert}
    • V ! v: GrphVertSet, . → GrphVert
    • V . i: GrphVertSet, RngIntElt → GrphVert
    • Index(v): GrphVert → RngIntElt
    • E ! { u, v}: GrphEdgeSet, { . } → GrphEdge
    • E ! [u, v]: GrphEdgeSet, [ . ] → GrphEdge
    • E . i: GrphEdgeSet, RngIntElt → GrphEdge
    • Example: Edge Sets
  • Operations on Vertex-Sets and Edge-Sets
    • # S: GrphVertSet → RngIntElt
    • # S: GrphEdgeSet → RngIntElt
    • s in S: GrphVert, GrphVertSet → BoolElt
    • s in S: GrphEdge, GrphEdgeSet → BoolElt
    • s notin S: GrphVert, GrphVertSet → BoolElt
    • s notin S: GrphEdge, GrphEdgeSet → BoolElt
    • S subset T: GrphVertSet, GrphVertSet → BoolElt
    • S subset T: GrphEdgeSet, GrphEdgeSet → BoolElt
    • S notsubset T: GrphVertSet, GrphVertSet → BoolElt
    • S notsubset T: GrphEdgeSet, GrphEdgeSet → BoolElt
    • S eq T: GrphVertSet, GrphVertSet → BoolElt
    • S eq T: GrphEdgeSet, GrphEdgeSet → BoolElt
    • s eq t: GrphVert, GrphVert → BoolElt
    • s eq t: GrphEdge, GrphEdge → BoolElt
    • S ne T: GrphVertSet, GrphVertSet → BoolElt
    • S ne T: GrphEdgeSet, GrphEdgeSet → BoolElt
    • s ne t: GrphVert, GrphVert → BoolElt
    • s ne t: GrphEdge, GrphEdge → BoolElt
    • ParentGraph(S): GrphVertSet → Grph
    • ParentGraph(S): GrphEdgeSet → Grph
    • ParentGraph(s): GrphVert → Grph
    • ParentGraph(s): GrphEdge → Grph
    • Random(S): GrphVertSet → GrphVert
    • Random(S): GrphEdgeSet → GrphEdge
    • Representative(S): GrphVertSet → GrphVert
    • Rep(S): GrphVertSet → GrphVert
    • Representative(S): GrphEdgeSet → GrphEdge
    • Rep(S): GrphEdgeSet → GrphEdge
    • for x in S do ... end for;
    • for random x in S do ... end for;
  • Operations on Edges and Vertices
    • EndVertices(e): GrphEdge → { GrphVert}
    • EndVertices(e): GrphEdge → [ GrphVert ]
    • InitialVertex(e): GrphEdge → GrphVert
    • TerminalVertex(e): GrphEdge → GrphVert
    • IncidentEdges(u): GrphVert → { GrphEdge}
• Labelled, Capacitated and Weighted Graphs
• Standard Constructions for Graphs
  • Subgraphs and Quotient Graphs
    • sub< G | list >: Grph, List → Grph, GrphVertSet, GrphEdgeSet
    • quo< G | P >: Grph, {{ GrphVert}} → Grph, GrphVertSet, GrphEdgeSet
    • Example: Subgraph
    • Example: Quotient
  • Incremental Construction of Graphs
    • Adding Vertices
      • G + n: Grph, RngIntElt → Grph
      • G +:= n: Grph, RngIntElt
      • AddVertex(~G): Grph
      • AddVertices(~G, n): Grph, RngIntElt
      • AddVertex(~G, l): Grph, .
      • AddVertices(~G, n, L): Grph, RngIntElt, SeqEnum
    • Removing Vertices
      • G - v: Grph, GrphVert → Grph
      • G - U: Grph, {  GrphVert } → Grph
      • G -:= v: Grph, GrphVert
      • G -:= U: Grph, {  GrphVert }
      • RemoveVertex(~G, v): Grph, GrphVert
      • RemoveVertices(~G, U): Grph, {  GrphVert }
    • Adding Edges
      • G + { u, v }: GrphUnd, { GrphVert, GrphVert } → GrphUnd, GrphEdge
      • G + [ u, v ]: GrphDir, [ GrphVert, GrphVert ] → GrphDir, GrphEdge
      • G + { { u, v } }: GrphUnd, { { GrphVert, GrphVert } } → GrphUnd
      • G + { [ u, v ] }: GrphDir, {  [ GrphVert, GrphVert ] } → GrphDir
      • G +:= { u, v }: GrphUnd, { GrphVert, GrphVert }
      • G +:= [ u, v ]: GrphDir, [ GrphVert, GrphVert ]
      • G +:= { { u, v } }: GrphUnd, { {  GrphVert, GrphVert  } }
      • G +:= { [ u, v ] }: GrphDir, {  [ GrphVert, GrphVert ] }
      • AddEdge(G, u, v): Grph, GrphVert, GrphVert → Grph, GrphEdge
      • AddEdge(G, u, v, l): Grph, GrphVert, GrphVert, . → Grph, GrphEdge
      • AddEdge(~G, u, v): Grph, GrphVert, GrphVert
      • AddEdge(~G, u, v, l): Grph, GrphVert, GrphVert, .
      • AddEdges(G, S): GrphUnd, { { GrphVert, GrphVert } } → GrphUnd
      • AddEdges(G, S): GrphDir, {  [  GrphVert, GrphVert ] } → GrphDir
      • AddEdges(G, S, L): Grph, SeqEnum, SeqEnum → Grph
      • AddEdges(~G, S): GrphUnd, { { GrphVert, GrphVert } }
      • AddEdges(~G, S): GrphDir, {  [  GrphVert, GrphVert ] }
      • AddEdges(~G, S, L): Grph, SeqEnum, SeqEnum
    • Removing Edges
      • G - e: Grph, GrphEdge → Grph
      • G - { e }: Grph, {  GrphEdge } → Grph
      • G - { { u, v } }: GrphUnd, { { GrphVert, GrphVert rbrace } → GrphUnd
      • G - { [u, v] }: GrphDir, {  [ GrphVert, GrphVert ] } → GrphDir
      • G -:= e: Grph, GrphEdge
      • G -:= { e }: Grph, {  GrphEdge }
      • G -:= { { u, v } }: GrphUnd, {  { GrphVert, GrphVert rbrace }
      • G -:= { [u, v] }: GrphDir, {  [ GrphVert, GrphVert ] }
      • RemoveEdge(~G, e): Grph, GrphEdge
      • RemoveEdges(~G, S): Grph, {  GrphEdge }
      • RemoveEdge(~G, u, v): Grph, GrphVert, GrphVert
      • RemoveEdges(~G, S): GrphDir, { {  GrphVert, GrphVert } }
      • RemoveEdges(~G, S): GrphDir, {  [  GrphVert, GrphVert ] }
  • Constructing Complements, Line Graphs; Contraction, Switching
    • Complement(G): Grph → Grph
    • Contract(e): GrphEdge → Grph
    • Contract(u, v): GrphVert, GrphVert → Grph
    • Contract(S): { GrphVert} → Grph
    • InsertVertex(e): GrphEdge → Grph
    • InsertVertex(T): { GrphEdge} → Grph
    • LineGraph(G): Grph → Grph
    • Switch(u): GrphVert → GrphUnd
    • Switch(S): { GrphVert} → Grph
    • Example: Grotzch
• Unions and Products of Graphs
  • Union(G, H): GrphUnd, GrphUnd → GrphUnd
  • Union(G, H): GrphDir, GrphDir → GrphDir
  • G join H: GrphDir, GrphDir → GrphDir
  • G join H: GrphUnd, GrphUnd → GrphUnd
  • EdgeUnion(G, H): GrphDir, GrphDir → GrphDir
  • EdgeUnion(G, H): GrphUnd, GrphUnd → GrphUnd
  • CompleteUnion(G, H): GrphDir, GrphDir → GrphDir
  • CompleteUnion(G, H): GrphUnd, GrphUnd → GrphUnd
  • CartesianProduct(G, H): GrphDir, GrphDir → GrphDir
  • CartesianProduct(G, H): GrphUnd, GrphUnd → GrphUnd
  • LexProduct(G, H): GrphDir, GrphDir → GrphDir
  • LexProduct(G, H): GrphUnd, GrphUnd → GrphUnd
  • TensorProduct(G, H): GrphDir, GrphDir → GrphDir
  • TensorProduct(G, H): GrphUnd, GrphUnd → GrphUnd
  • G ^ n: GrphUnd, RngIntElt → GrphUnd
• Converting between Graphs and Digraphs
  • OrientatedGraph(G): GrphUnd → GrphDir
  • UnderlyingGraph(D): Grph → GrphUnd
  • UnderlyingDigraph(G): Grph → GrphDir
• Construction from Groups, Codes and Designs
  • Graphs Constructed from Groups
    • CayleyGraph(A : parameter): Grp → Grph, GrphVertSet, GrphEdgeSet
    • SchreierGraph(A, B): Grp, Grp → Grph, GrphVertSet, GrphEdgeSet
    • OrbitalGraph(P, u, T): GrpPerm, RngIntElt, { RngIntElt} → GrphUnd
    • ClosureGraph(P, G): GrpPerm, GrphUnd → GrphUnd
    • PaleyGraph(q): RngIntElt → GrphUnd
    • PaleyTournament(q): RngIntElt → GrphDir
  • Graphs Constructed from Designs
    • IncidenceGraph(D): Inc → GrphUnd
    • PointGraph(D): Inc → GrphUnd
    • BlockGraph(D): Inc → GrphUnd
    • IncidenceGraph(P): Plane → GrphUnd
    • PointGraph(P): Plane → GrphUnd;
    • LineGraph(P): Plane → GrphUnd
    • HadamardGraph(H : parameters): Mtrx → GrphUnd
  • Miscellaneous Graph Constructions
    • Converse(G): GrphDir → GrphDir
    • OddGraph(n): RngIntElt → GrphUnd
    • TriangularGraph(n): RngIntElt → GrphUnd
    • SquareLatticeGraph(n): RngIntElt → GrphUnd
    • ClebschGraph() → GrphUnd
    • ShrikhandeGraph() → GrphUnd
    • GewirtzGraph() → GrphUnd
    • ChangGraphs() → [GrpUnd, GrpUnd, GrpUnd]
• Elementary Invariants of a Graph
  • Order(G): Grph → RngIntElt
  • NumberOfVertices(G): Grph → RngIntElt
  • Size(G): Grph → RngIntElt
  • NumberOfEdges(G): Grph → RngIntElt
  • CharacteristicPolynomial(G): GrphUnd → RngUPolElt
  • Spectrum(G): GrphUnd → SetEnum
• Elementary Graph Predicates
  • u adj v: GrphVert, GrphVert → BoolElt
  • e adj f: GrphEdge, GrphEdge → BoolElt
  • u notadj v: GrphVert, GrphVert → BoolElt
  • e notadj f: GrphEdge, GrphEdge → BoolElt
  • u in e: GrphVert, GrphEdge → BoolElt
  • u notin e: GrphVert, GrphEdge → BoolElt
  • G eq H: GrphDir, GrphDir → BoolElt
  • G eq H: GrphUnd, GrphUnd → BoolElt
  • IsSubgraph(G, H): Grph, Grph → BoolElt
  • IsBipartite(G): GrphUnd → BoolElt
  • IsComplete(G): Grph → BoolElt
  • IsEulerian(G): Grph → BoolElt
  • IsForest(G): GrphUnd → BoolElt
  • IsEmpty(G): Grph → BoolElt
  • IsNull(G): Grph → BoolElt
  • IsPath(G): Grph → BoolElt
  • IsPolygon(G): Grph → BoolElt
  • IsRegular(G): Grph → BoolElt
  • IsTree(G): Grph → BoolElt
• Adjacency and Degree
  • Adjacency and Degree Functions for a Graph
    • Degree(u): GrphVert → RngIntElt
    • Alldeg(G, n): GrphUnd, RngIntElt → { GrphVert}
    • MaximumDegree(G): GrphUnd → RngIntElt, GrphVert
    • Maxdeg(G): GrphUnd → RngIntElt, GrphVert
    • MinimumDegree(G): GrphUnd → RngIntElt, GrphVert
    • Mindeg(G): GrphUnd → RngIntElt, GrphVert
    • DegreeSequence(G): Grph → [ { GrphVert} ]
    • Valence(G): GrphUnd → RngIntElt
    • Neighbours(u): GrphVert → { GrphVert}
    • Neighbors(u): GrphVert → { GrphVert}
    • IncidentEdges(u): GrphVert → { GrphEdge}
    • Bipartition(G): GrphUnd → [ { GrphVert} ]
    • MinimumDominatingSet(G): GrphUnd → SetEnum
  • Adjacency and Degree Functions for a Digraph
    • InDegree(u): GrphVert → RngIntElt
    • OutDegree(u): GrphVert → RngIntElt
    • Degree(u): GrphVert → RngIntElt
    • Alldeg(G, n): GrphDir, RngIntElt → { GrphVert}
    • MaximumInDegree(G): GrphDir → RngIntElt, GrphVert
    • Maxindeg(G): GrphDir → RngIntElt, GrphVert
    • MaximumOutDegree(G): GrphDir → RngIntElt, GrphVert
    • Maxoutdeg(G): GrphDir → RngIntElt, GrphVert
    • MinimumInDegree(G): GrphDir → RngIntElt, GrphVert
    • Minindeg(G): GrphDir → RngIntElt, GrphVert
    • MinimumOutDegree(G): GrphDir → RngIntElt, GrphVert
    • Minoutdeg(G): GrphDir → RngIntElt, GrphVert
    • MaximumDegree(G): GrphDir → RngIntElt, GrphVert
    • Maxdeg(G): GrphDir → RngIntElt, GrphVert
    • MinimumDegree(G): GrphDir → RngIntElt, GrphVert
    • Mindeg(G): GrphDir → RngIntElt, GrphVert
    • DegreeSequence(G): Grph → [ { GrphVert} ]
    • InNeighbours(u): GrphVert → { GrphVert}
    • InNeighbors(u): GrphVert → { GrphVert}
    • OutNeighbours(u): GrphVert → { GrphVert}
    • OutNeighbors(u): GrphVert → { GrphVert}
    • IncidentEdges(u): GrphVert → { GrphEdge}
• Connectedness
  • Connectedness in a Graph
    • IsConnected(G): GrphUnd → BoolElt
    • Components(G): GrphUnd → [ { GrphVert} ]
    • Component(u): GrphVert → Grph
    • IsSeparable(G): GrphUnd → BoolElt
    • IsBiconnected(G): GrphUnd → BoolElt
    • CutVertices(G): Grph → { GrphVert}
    • Bicomponents(G): GrphUnd → [GrphUnd]
  • Connectedness in a Digraph
    • IsStronglyConnected(G): GrphDir → BoolElt
    • IsWeaklyConnected(G): GrphDir → BoolElt
    • StronglyConnectedComponents(G): GrphDir → [ { GrphVert} ]
    • Component(u): GrphVert → Grph
  • Graph Triconnectivity
    • IsTriconnected(G): GrphUnd → BoolElt
    • Splitcomponents(G): GrphUnd → [ { GrphVert } ], [ [ GrphVert ]]
    • SeparationVertices(G): GrphUnd → [ [ GrphVert ]], [ { GrphVert} ]
    • Example: Triconnectivity
  • Maximum Matching in Bipartite Graphs
    • MaximumMatching(G): GrphUnd → [ { GrphEdge} ]
    • Example: Max Matching
  • General Vertex and Edge Connectivity in Graphs and Digraphs
    • VertexSeparator(G): Grph → [ GrphVert ]
    • VertexConnectivity(G): Grph → RngIntElt, [ GrphVert ]
    • IsKVertexConnected(G, k): Grph, RngIntElt → BoolElt
    • EdgeSeparator(G): Grph → [ GrphEdge ]
    • EdgeConnectivity(G): Grph → RngIntElt, [ GrphEdge ]
    • IsKEdgeConnected(G, k): Grph, RngIntElt → BoolElt
    • Example: Connectivity
• Distances, Paths and Circuits in a Graph
  • Distances, Paths and Circuits in a Possibly Weighted Graph
    • Reachable(u, v): GrphVert, GrphVert → BoolElt
    • Distance(u, v): GrphVert, GrphVert → RngIntElt
    • Geodesic(u, v): GrphVert, GrphVert → [GrphVert]
  • Distances, Paths and Circuits in a Non-Weighted Graph
    • Diameter(G): Grph → RngIntElt
    • DiameterPath(G): Grph → [GrphVert]
    • Ball(u, n): GrphVert, RngIntElt → { GrphVert}
    • Sphere(u, n): GrphVert, RngIntElt → { GrphVert}
    • DistancePartition(u): GrphVert → [ { GrphVert} ]
    • IsEquitable(G, P): GrphUnd, { { GrphVert}} → BoolElt
    • IsEquitable(G, P): GrphUnd, { { RngIntElt}} → BoolElt
    • EquitablePartition(P, G): { { GrphVert}}, GrphUnd → { { GrphVert}}
    • EquitablePartition(P, G): { { RngIntElt}}, GrphUnd → { { GrphVert}}
    • Girth(G): GrphUnd → RngIntElt
    • GirthCycle(G): GrphUnd → [GrphVert]
• Maximum Flow, Minimum Cut, and Shortest Paths
• Matrices and Vector Spaces Associated with a Graph or Digraph
  • AdjacencyMatrix(G): Grph → AlgMatElt
  • DistanceMatrix(G): Grph → AlgMatElt
  • IncidenceMatrix(G): Grph → ModHomElt
  • IntersectionMatrix(G, P): GrphUnd, { { GrphVert}} → AlgMatElt
  • IntersectionMatrix(G, P): GrphUnd, { { RngIntElt}} → AlgMatElt
• Spanning Trees of a Graph or Digraph
  • SpanningTree(G): GrphUnd → Grph, GrphVertSet, GrphEdgeSet
  • SpanningForest(G): Grph → Grph, GrphVertSet, GrphEdgeSet
  • BreadthFirstSearchTree(u): GrphVert → Grph, GrphVertSet, GrphEdgeSet
  • BFSTree(u): GrphVert → Grph
  • DepthFirstSearchTree(u): GrphVert → Grph, GrphVertSet, GrphEdgeSet, SeqEnum
  • DFSTree(u): GrphVert → Grph, GrphVertSet, GrphEdgeSet, SeqEnum
• Directed Trees
  • IsRootedTree(G): GrphDir → BoolElt, GrphVert
  • Root(G): GrphDir → GrphVert
  • IsRoot(v): GrphVert → BoolElt
  • RootSide(v): GrphVert → GrphVert
  • VertexPath(u,v): GrphVert, GrphVert → SeqEnum
  • BranchVertexPath(u,v): GrphVert, GrphVert → SeqEnum
• Colourings
  • ChromaticNumber(G): GrphUnd → RngIntElt
  • OptimalVertexColouring(G): GrphUnd → SeqEnum
  • ChromaticIndex(G): GrphUnd → RngIntElt
  • OptimalEdgeColouring(G): GrphUnd → SeqEnum
  • ChromaticPolynomial(G): GrphUnd → RngUPolElt
  • Example: Chromatic Number
• Cliques, Independent Sets
  • HasClique(G, k): GrphUnd, RngIntElt → BoolElt, { GrphVert }
  • HasClique(G, k, m : parameters): GrphUnd, RngIntElt, BoolElt → BoolElt, { GrphVert }
  • HasClique(G, k, m, f : parameters): GrphUnd, RngIntElt, BoolElt, RngIntElt → BoolElt, { GrphVert }
  • MaximumClique(G : parameters): GrphUnd → { GrphVert }
  • CliqueNumber(G : parameters): GrphUnd → RngIntElt
  • AllCliques(G : parameters): GrphUnd → SeqEnum
  • AllCliques(G, k : parameters): GrphUnd, RngIntElt → SeqEnum
  • AllCliques(G, k, m : parameters): GrphUnd, RngIntElt, BoolElt → SeqEnum
  • MaximumIndependentSet(G: parameters): GrphUnd → { GrphVert }
  • IndependenceNumber(G: parameters): GrphUnd → RngIntElt
  • Example: Cliques
• Planar Graphs
  • IsPlanar(G): GrphUnd → BoolElt, GrphUnd
  • Obstruction(G): GrphUnd → GrphUnd
  • IsHomeomorphic(G : parameters): GrphUnd → BoolElt
  • Faces(G): GrphUnd → SeqEnum[GrphVert]
  • Face(u, v): GrphVert, GrphVert → SeqEnum
  • Face(e): GrphEdge → SeqEnum
  • NFaces(G): GrphUnd → RngIntElt
  • NumberOfFaces(G): GrphUnd → RngIntElt
  • Embedding(G): GrphUnd → SeqEnum
  • Embedding(v): GrphVert → SeqEnum
  • PlanarDual(G): GrphUnd → GrphUnd
  • Example: Planarity
• Automorphism Group of a Graph or Digraph
  • The Automorphism Group Function
    • AutomorphismGroup(G : parameters): Grph → GrpPerm, GSet, GSet, PowMap, Map, Grph
  • nauty Invariants
    • IsPartitionRefined(G: parameters): Grph → BoolElt
  • Graph Colouring and Automorphism Group
  • Variants of Automorphism Group
    • CanonicalGraph(G): Grph → Grph
    • EdgeGroup(G): Grph → GrpPerm, GSet
    • IsIsomorphic(G, H : parameters ): GrphDir, GrphDir → BoolElt, Map
    • IsIsomorphic(G, H : parameters ): GrphUnd, GrphUnd → BoolElt, Map
    • Example: Automorphism Group
    • Example: Graph Isomorphim
  • Action of Automorphisms
    • Image(a, Y, y): GrpPermElt, GSet, Elt → Elt
    • Orbit(A, Y, y): GrpPerm, GSet, Elt → GSet
    • Orbits(A, Y): GrpPerm, GSet → [ GSet ]
    • Stabilizer(A, Y, y): GrpPerm, GSet, Elt → GrpPerm
    • Action(A, Y): GrpPerm, GSet → Hom(Grp), GrpPerm, GrpPerm
    • ActionImage(A, Y): GrpPerm, GSet → GrpPerm
    • ActionKernel(A, Y): GrpPerm, GSet → GrpPerm
    • Example: Automorphism Action
• Symmetry and Regularity Properties of Graphs
  • IsTransitive(G): GrphUnd → BoolElt
  • IsVertexTransitive(G): GrphUnd → BoolElt
  • IsEdgeTransitive(G): GrphUnd → BoolElt
  • OrbitsPartition(G): GrphUnd → [ { GrphVert} ]
  • IsPrimitive(G): GrphUnd → BoolElt
  • IsSymmetric(G): GrphUnd → BoolElt
  • IsDistanceTransitive(G): GrphUnd → BoolElt
  • IsDistanceRegular(G): GrphUnd → BoolElt
  • IntersectionArray(G): GrphUnd → [RngIntElt]
  • Example: Regularity
• Graph Databases and Graph Generation
  • Strongly Regular Graphs
    • StronglyRegularGraphsDatabase() → DB
    • Classes(D): DB → SeqEnum
    • NumberOfClasses(D): DB → RngIntElt
    • NumberOfGraphs(D): DB → RngIntElt
    • NumberOfGraphs(D, S): DB, SeqEnum → RngIntElt
    • Graphs(D, S): DB, SeqEnum → SeqEnum
    • Graph(D, S, i): DB, SeqEnum, RngIntElt → GrphUnd
    • RandomGraph(D): DB → GrphUnd
    • RandomGraph(D, S): DB, SeqEnum → GrphUnd
    • for G in D do ... end for;
    • Example: Strongly Regular Graphs
  • Small Graphs
    • Creation of Small Graph Databases
      • SmallGraphDatabase(n : parameters): RngIntElt → DB
      • EulerianGraphDatabase(n : parameters): RngIntElt → DB
      • PlanarGraphDatabase(n): RngIntElt → DB
      • SelfComplementaryGraphDatabase(n): RngIntElt → DB
    • Access functions
      • # D: DB → RngIntElt
      • Graph(D, i): DB, RngIntElt → GrphUnd
      • Random(D): DB → GrphUnd
      • for G in D do ... end for;
  • Generating Graphs
    • GenerateGraphs(n : parameters): RngIntElt → IO
    • NextGraph(I: parameters): IO → BoolElt, GrphUnd
    • Example: Graph Generation
  • A General Facility
    • OpenGraphFile(s, f, p): MonStgElt, RngIntElt, RngIntElt → IO
    • Example: Graph General Access