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\ {\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.

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.

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), \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.

> 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 ]

Run in calculator

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

Run in calculator