Construction from Groups, Codes and Designs

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 \(\Omega = \{1,\ldots,n\}\). Let \(u\) be an element of \(\Omega\) and let \(T = \{t_1, \ldots, t_r\}\) be a subset of \(\Omega\). This function constructs the underlying graph \(G\) of the digraph corresponding to the union of \(P\)-orbits containing the pairs \((u, t_1), \ldots, (u, t_r)\). Thus, if \(T\) defines a self-paired orbit \(\Delta\) of the stabilizer in \(P\) of the point \(u\), this function constructs the orbital graph associated with \(\Delta\).

ClosureGraph(P, G): GrpPerm, GrphUnd -> GrphUnd

Let \(P\) be a permutation group acting on the set \(\Omega = \{1,\ldots,n\}\). Let \(G\) be a graph (digraph) with vertices \(v_1, \ldots, v_n\). 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 \({\bf F}_{q}\) where \(q\) must be a prime power equivalent to 1 mod 4. Vertices are in bijection with elements of \({\bf F}_{q}\) and distinct elements are adjacent when their difference is a square in the field.

PaleyTournament(q): RngIntElt -> GrphDir

The Paley tournament of \({\bf F}_{q}\) where \(q\) must be a prime power equivalent to 3 mod 4. Vertices are in bijection with elements of \({\bf F}_{q}\) and there is an edge from \(u\) to \(v\) when \(u \ne v\) and \(v - u\) is a square in the field.

Graphs Constructed from Designs

IncidenceGraph(D): Inc -> GrphUnd

Given an incidence structure \(D = (X, \cal{B})\), construct the incidence graph \(G\) of \(D\). The vertices of \(G\) is \(X \cup \cal{B}\). The adjacency rules are as follows: No two vertices of \(X\) are adjacent; no two vertices of \(\cal{B}\) are adjacent; a vertex \(x \in X\) is adjacent to a vertex \(B \in \cal{B}\) if and only if \(x \in B\).

PointGraph(D): Inc -> GrphUnd

Given an incidence structure \(D = (X, \cal{B})\), construct the point graph \(G\) of \(D\). The vertex-set of \(G\) is \(X\). Vertices \(x \in X\), \(y \in X\) are adjacent in \(G\) if there is a block \(B\in \cal{B}\) such that \(x \in B\) and \(y \in 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 \cup L\). The adjacency rules are as follows: No two vertices of \(V\) are adjacent; no two vertices of \(L\) are adjacent; a vertex \(v \in V\) is adjacent to a vertex \(a \in 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 \in 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 line graph \(G\) of \(P\). The vertex-set of \(G\) is \(L\). Lines \(a, b \in 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 \(\pm 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 \(n\)th 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 \(n\)th 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 \(n\)th square lattice graph. This is the cartesian product of the \(n\)th 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.