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.
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.
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.
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.
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 adj v and w adj t, there exists an automorphism a such ua = w and va = t. To see which automorphism group is computed see Subsection Graph Colouring and Automorphism Group.
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 ua = w and va = t. To see which automorphism group is computed see Subsection Graph Colouring and Automorphism Group.
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.
IntersectionArray(G) : GrphUnd -> [RngIntElt]
The intersection array of the distance regular graph G. This is returned as a sequence [ k, b(1), ..., b(d - 1), 1, c(2), ..., 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 Nj(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 Nj - 1(v) that are adjacent to u, (1 ≤j ≤d),
and b(j) = number of vertices in Nj + 1(v) that are adjacent to u (0 ≤j ≤d - 1).

Example Graph_Regularity (H158E21)

We illustrate the use of some of the symmetry functions by applying then to the graph of the 8-dimensional cube. 
> 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: 
> 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
V2.28, 13 July 2023