# Construction from Groups, Codes and Designs ## Graphs Constructed from Groups ### `CayleyGraph(A : parameter): Grp -> Grph, GrphVertSet, GrphEdgeSet` ```magma 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` ```magma 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` ```magma 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.