# Symmetry and Regularity Properties of Graphs

## `IsTransitive(G): GrphUnd -> BoolElt`

## `IsVertexTransitive(G): GrphUnd -> BoolElt`

Returns `true` if the automorphism group of the graph $G$ is transitive, otherwise `false`. To see which automorphism group is computed see Subsection [Graph Colouring and Automorphism Group](automorphism-group-graph.md#graph-subsec-auto-grp-colours).

## `IsEdgeTransitive(G): GrphUnd -> BoolElt`

Returns `true` if the automorphism group of the graph $G$ is transitive on the edges of $G$ (i.e. if the edge group of $G$ is transitive). To see which automorphism group is computed see Subsection [Graph Colouring and Automorphism Group](automorphism-group-graph.md#graph-subsec-auto-grp-colours).

## `OrbitsPartition(G): GrphUnd -> [ { GrphVert} ]`

Given a graph $G$, return the partition of its vertex-set corresponding to the orbits of its automorphism group in the form of a set system. To see which automorphism group is computed see Subsection [Graph Colouring and Automorphism Group](automorphism-group-graph.md#graph-subsec-auto-grp-colours).

## `IsPrimitive(G): GrphUnd -> BoolElt`

Returns `true` if the graph $G$ is primitive, i.e. if its automorphism group is primitive. To see which automorphism group is computed see Subsection [Graph Colouring and Automorphism Group](automorphism-group-graph.md#graph-subsec-auto-grp-colours).

## `IsSymmetric(G): GrphUnd -> BoolElt`

Returns `true` if the graph $G$ is symmetric, i.e. if for all pairs of vertices $u$, $v$ and $w$, $t$ such that $u\ {\operatorname{adj}}v$ and $w\ {\operatorname{adj}}t$, there exists an automorphism $a$ such $u^a = w$ and $v^a = t$. To see which automorphism group is computed see Subsection [Graph Colouring and Automorphism Group](automorphism-group-graph.md#graph-subsec-auto-grp-colours).

## `IsDistanceTransitive(G): GrphUnd -> BoolElt`

Returns `true` if the connected graph $G$ is distance transitive i.e. if for all vertices $u$, $v$, $w$, $t$ of $G$ such that $d(u, v) = d(w, t)$, there is an automorphism $a$ in $A$ such that $u^a = w$ and $v^a = t$. To see which automorphism group is computed see Subsection [Graph Colouring and Automorphism Group](automorphism-group-graph.md#graph-subsec-auto-grp-colours).

## `IsDistanceRegular(G): GrphUnd -> BoolElt`

Returns `true` if the graph $G$ is distance regular, otherwise `false`. To see how the automorphism group of $G$ is computed see Subsection [Graph Colouring and Automorphism Group](automorphism-group-graph.md#graph-subsec-auto-grp-colours).

## `IntersectionArray(G): GrphUnd -> [RngIntElt]`

The intersection array of the distance regular graph $G$. This is returned as a sequence $[ k, b(1), \ldots, b(d-1), 1, c(2),\ldots, c(d) ]$ where $k$ is the valency of the graph, $d$ is the diameter of the graph, and the numbers $b(i)$ and $c(i)$ are defined as follows: Let $N_j(u)$ denote the set of vertices of $G$ that lie at distance $j$ from vertex $u$. Let $u$ and $v$ be a pair of vertices satisfying $d(u, v) = j$.

Then $c(j)$ = number of vertices in $N_{j-1}(v)$ that are adjacent to $u$, ($1 \leq j \leq d$), and $b(j)$ = number of vertices in $N_{j+1}(v)$ that are adjacent to $u$ ($0 \leq j \leq d-1$).

## `Example: Regularity (ex-2c631b)`

We illustrate the use of some of the symmetry functions by applying then to the graph of the 8-dimensional cube.

```magma
> g := KCubeGraph(8);
> IsVertexTransitive(g);
true
> IsEdgeTransitive(g);
true
> IsSymmetric(g);
true
> IsDistanceTransitive(g);
true
> IntersectionArray(g);
[ 8, 7, 6, 5, 4, 3, 2, 1, 1, 2, 3, 4, 5, 6, 7, 8 ]

```

We also see that the functions using the graph’s automorphism group are dependent upon the graph being coloured or not:

```magma
> q := 9;
> P := FiniteProjectivePlane(q);
> X := IncidenceGraph(P);
>
> Order(X);
182
> Valence(X);
10
> Diameter(X);
3
> Girth(X);
6
> O1 := OrbitsPartition(X);
> IsSymmetric(X);
true
>
> Labels := [ "a" : i in [1..96] ];
> #Labels;
96
> AssignLabels(VertexSet(X), Labels);
> O2 := OrbitsPartition(X);
> O2 eq O1;
false
> IsSymmetric(X);
false

```