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 := trueby default) can be set tofalseto 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 := trueby 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
LabelledandDirected, which are bothtrueby 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\).
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
Labelsis set tofalseby default, but when set totrue, 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.