Construction from Groups, Codes and Designs

Contents

Graphs Constructed from Groups

CayleyGraph(A : parameter) : Grp -> Grph, GrphVertSet, GrphEdgeSet
    Labelled: BoolElt                   Default: true
    Directed: BoolElt                   Default: true
Given a finite group A defined on generating set X, construct the Cayley graph C of A relative to the generating set X. This graph is defined as follows: The vertices correspond to the elements of A and two vertices u, v are adjacent if and only if there exists an element x in X such that u * x = v.

The optional parameter Labelled (Labelled := true by default) can be set to false to prevent the graph being labelled. If this is not done, then the vertices of C will be labelled with the appropriate elements of A and the (directed) edge from u to v will be labelled with the appropriate element x as defined above.

The parameter Directed (Directed := true by default) may be used to return the Cayley graph of G as an undirected graph

SchreierGraph(A, B) : Grp, Grp -> Grph, GrphVertSet, GrphEdgeSet
    Labelled: BoolElt                   Default: true
    Directed: BoolElt                   Default: true
Given a finite group A defined on the generating set X and a subgroup B of A, construct the Schreier coset graph S for A over B, relative to X. The graph S is defined as follows: The vertices correspond to the cosets of B in A, and two vertices u, v are adjacent in S if and only if there exists an element x in X such that u * x = v.

The graph is available in both a labelled and an unlabelled version and directed and undirected versions. These versions are controlled by the parameters Labelled and Directed, which are both true by default.

OrbitalGraph(P, u, T) : GrpPerm, RngIntElt, { RngIntElt } -> GrphUnd
Let P be a transitive permutation group acting on the set Ω = {1, ..., n}. Let u be an element of Ω and let T = {t1, ..., tr} be a subset of Ω. This function constructs the underlying graph G of the digraph corresponding to the union of P-orbits containing the pairs (u, t1), ..., (u, tr). Thus, if T defines a self-paired orbit Δ of the stabilizer in P of the point u, this function constructs the orbital graph associated with Δ.
ClosureGraph(P, G) : GrpPerm, GrphUnd -> GrphUnd
Let P be a permutation group acting on the set Ω = {1, ..., n}. Let G be a graph (digraph) with vertices v1, ..., vn. This function adds the minimum number of edges to G so as to produce a graph (digraph) H which is left invariant by the group P.
PaleyGraph(q) : RngIntElt -> GrphUnd
The Paley graph of GF(q) where q must be a prime power equivalent to 1 mod 4. Vertices are in bijection with elements of GF(q) and distinct elements are adjacent when their difference is a square in the field.
PaleyTournament(q) : RngIntElt -> GrphDir
The Paley tournament of GF(q) where q must be a prime power equivalent to 3 mod 4. Vertices are in bijection with elements of GF(q) and there is an edge from u to v when u ≠v and v - u is a square in the field.

Graphs Constructed from Designs

IncidenceGraph(D) : Inc -> GrphUnd
Given an incidence structure D = (X, B), construct the incidence graph G of D. The vertices of G is X ∪B. The adjacency rules are as follows: No two vertices of X are adjacent; no two vertices of B are adjacent; a vertex x ∈X is adjacent to a vertex b ∈B if and only if x is in b.
PointGraph(D) : Inc -> GrphUnd
Given an incidence structure D = (X, B), construct the point graph G of D. The vertex-set of G is X. Vertices x ∈X, y ∈X are adjacent in G if there is a block b∈B such that x ∈b and y ∈b.
BlockGraph(D) : Inc -> GrphUnd
The block graph of the incidence structure D; i.e. the point graph of the dual of D.
IncidenceGraph(P) : Plane -> GrphUnd
Given a plane P with point-set V and line-set L, construct the incidence graph G of P. The vertex-set of G is V ∪L. The adjacency rules are as follows: No two vertices of V are adjacent; no two vertices of L are adjacent; a vertex v ∈V is adjacent to a vertex a ∈L if and only if v lies on a.
PointGraph(P) : Plane -> GrphUnd;
Given a plane P with point-set V and line-set L, construct the point graph G of P. The vertex-set of G is V. Vertices u, v ∈V are adjacent in G iff there is a line in L that contains them both.
LineGraph(P) : Plane -> GrphUnd
Given a plane P with point-set V and line-set L, construct the point graph G of P. The vertex-set of G is L. Lines a, b ∈L are adjacent in G iff there is a vertex in V that lies on them both.
HadamardGraph(H : parameters) : Mtrx -> GrphUnd
    Labels: BoolElt                     Default: false
The graph of the ∓ 1 matrix H as described in Brendan D. McKay's note "Hadamard equivalence via graph isomorphism" (with self-loops omitted). The parameter Labels is set to false by default, but when set to true, the vertices associated with rows are labelled "row" and the others "col". Those labelled "row" are those given loops in McKay's paper.

Miscellaneous Graph Constructions

Converse(G) : GrphDir -> GrphDir
Returns the converse H of the directed graph G: if [u, v] is an edge of G then [v, u] is an edge of H.
OddGraph(n) : RngIntElt -> GrphUnd
The nth odd graph. Vertices are (n - 1)--subsets of a (2n - 1)-set with vertices adjacent if and only if the (n - 1)--subsets are disjoint.
TriangularGraph(n) : RngIntElt -> GrphUnd
The nth triangular graph. Vertices are 2-subsets of a n-set with vertices adjacent if and only if the 2-subsets are unequal and not disjoint.
SquareLatticeGraph(n) : RngIntElt -> GrphUnd
The nth square lattice graph. This is the cartesian product of the nth complete graph with itself.
ClebschGraph() : -> GrphUnd
ShrikhandeGraph() : -> GrphUnd
GewirtzGraph() : -> GrphUnd
Return the named graph.
ChangGraphs() : -> [GrpUnd, GrpUnd, GrpUnd]
Return a sequence of the three Chang graphs.
V2.28, 13 July 2023