---
title: "Construction from Groups, Codes, and Designs"
canonical: "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/group-code-design.html"
source: "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/group-code-design.md"
part: "Combinatorics"
chapter: "Graphs"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "https://docs.magma-maths.org/v2.30-1/index.md"}
  - {"title": "Combinatorics", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/index-combinatorics.md"}
  - {"title": "Graphs", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/index-graphs.md"}
prev: {"title": "Converting between Graphs and Digraphs", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/conversion-graph-digraph.md"}
next: {"title": "Elementary Invariants of a Graph", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/invariant.md"}
intrinsics:
  - {"name": "CayleyGraph", "signature": "CayleyGraph(A : parameter): Grp -> Grph, GrphVertSet, GrphEdgeSet"}
  - {"name": "SchreierGraph", "signature": "SchreierGraph(A, B): Grp, Grp -> Grph, GrphVertSet, GrphEdgeSet"}
  - {"name": "OrbitalGraph", "signature": "OrbitalGraph(P, u, T): GrpPerm, RngIntElt, { RngIntElt} -> GrphUnd"}
  - {"name": "ClosureGraph", "signature": "ClosureGraph(P, G): GrpPerm, GrphUnd -> GrphUnd"}
  - {"name": "PaleyGraph", "signature": "PaleyGraph(q): RngIntElt -> GrphUnd"}
  - {"name": "PaleyTournament", "signature": "PaleyTournament(q): RngIntElt -> GrphDir"}
  - {"name": "IncidenceGraph", "signature": "IncidenceGraph(D): Inc -> GrphUnd"}
  - {"name": "PointGraph", "signature": "PointGraph(D): Inc -> GrphUnd"}
  - {"name": "BlockGraph", "signature": "BlockGraph(D): Inc -> GrphUnd"}
  - {"name": "IncidenceGraph", "signature": "IncidenceGraph(P): Plane -> GrphUnd"}
  - {"name": "PointGraph", "signature": "PointGraph(P): Plane -> GrphUnd;"}
  - {"name": "LineGraph", "signature": "LineGraph(P): Plane -> GrphUnd"}
  - {"name": "HadamardGraph", "signature": "HadamardGraph(H : parameters): Mtrx -> GrphUnd"}
  - {"name": "Converse", "signature": "Converse(G): GrphDir -> GrphDir"}
  - {"name": "OddGraph", "signature": "OddGraph(n): RngIntElt -> GrphUnd"}
  - {"name": "TriangularGraph", "signature": "TriangularGraph(n): RngIntElt -> GrphUnd"}
  - {"name": "SquareLatticeGraph", "signature": "SquareLatticeGraph(n): RngIntElt -> GrphUnd"}
  - {"name": "ClebschGraph", "signature": "ClebschGraph() -> GrphUnd"}
  - {"name": "ShrikhandeGraph", "signature": "ShrikhandeGraph() -> GrphUnd"}
  - {"name": "GewirtzGraph", "signature": "GewirtzGraph() -> GrphUnd"}
  - {"name": "PetersenGraph", "signature": "PetersenGraph() -> GrphUnd"}
  - {"name": "ChangGraphs", "signature": "ChangGraphs() -> [GrpUnd, GrpUnd, GrpUnd]"}
---

<a id="group-code-design"></a>
<a id="graph-sec-code-design"></a>
# Construction from Groups, Codes, and Designs

## Graphs Constructed from Groups

<a id="function-cayleygraph-grp"></a>
### `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

<a id="function-schreiergraph-grp-grp"></a>
### `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.

<a id="function-orbitalgraph-grpperm-rngintelt-rngintelt"></a>
### `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$.

<a id="function-closuregraph-grpperm-grphund"></a>
### `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$.

<a id="function-paleygraph-rngintelt"></a>
### `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.

<a id="function-paleytournament-rngintelt"></a>
### `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

<a id="function-incidencegraph-inc"></a>
### `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$.

<a id="function-pointgraph-inc"></a>
### `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$.

<a id="function-blockgraph-inc"></a>
### `BlockGraph(D): Inc -> GrphUnd`

The block graph of the incidence structure $D$; i.e. the point graph of the dual of $D$.

<a id="function-incidencegraph-plane"></a>
### `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$.

<a id="function-pointgraph-plane"></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.

<a id="function-linegraph-plane"></a>
### `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.

<a id="function-hadamardgraph-mtrx"></a>
### `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

<a id="function-converse-grphdir"></a>
### `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$.

<a id="function-oddgraph-rngintelt"></a>
### `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.

<a id="function-triangulargraph-rngintelt"></a>
### `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.

<a id="function-squarelatticegraph-rngintelt"></a>
### `SquareLatticeGraph(n): RngIntElt -> GrphUnd`

The $n$th square lattice graph. This is the cartesian product of the $n$th complete graph with itself.

<a id="function-clebschgraph"></a>
### `ClebschGraph() -> GrphUnd`

<a id="function-shrikhandegraph"></a>
### `ShrikhandeGraph() -> GrphUnd`

<a id="function-gewirtzgraph"></a>
### `GewirtzGraph() -> GrphUnd`

<a id="function-petersengraph"></a>
### `PetersenGraph() -> GrphUnd`

Return the named graph.

<a id="function-changgraphs"></a>
### `ChangGraphs() -> [GrpUnd, GrpUnd, GrpUnd]`

Return a sequence of the three Chang graphs.
