Symmetry and Regularity Properties of Graphs

IsTransitive(G : parameters) : GrphUnd -> BoolElt

IsVertexTransitive(G : parameters) : GrphUnd -> BoolElt

Returns true if the automorphism group of the graph G is transitive, otherwise false. The parameters which can be passed are:

     Invariant: MonStgElt                Default: 

     Minlevel: RngIntElt                 Default: 0

     Maxlevel: RngIntElt                 Default: 

     Arg: RngIntElt                      Default: 

     IgnoreLabels: BoolElt               Default: false

Their meaning is described in AutomorphismGroup.

IsEdgeTransitive(G : parameters) : 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). The parameters are as in IsTransitive.

OrbitsPartition(G : parameters ) : 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. The parameters are almost identical to those for AutomorphismGroup (with the exception of Canonical which is irrelevant here and of the printing facilities).

IsPrimitive(G : parameters) : GrphUnd -> BoolElt

    Invariant: MonStgElt                Default: 

    Minlevel: RngIntElt                 Default: 0

    Maxlevel: RngIntElt                 Default: 

    Arg: RngIntElt                      Default: 

    IgnoreLabels: BoolElt               Default: false

Returns true if the graph G is primitive, i.e. if its automorphism group is primitive. The parameters are as in IsTransitive.

IsSymmetric(G : parameters) : GrphUnd -> BoolElt

    Invariant: MonStgElt                Default: 

    Minlevel: RngIntElt                 Default: 0

    Maxlevel: RngIntElt                 Default: 

    Arg: RngIntElt                      Default: 

    IgnoreLabels: BoolElt               Default: false

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 u^a = w and v^a = t. The parameters are as in IsTransitive.

[Future release] IsArcTransitive(G, t) : GrphUnd, RngIntElt -> BoolElt

Returns true if the graph G is t-arc transitive, i.e. if the automorphism group A of G is transitive on the set of t--arcs of G but not transitive on the set of (t + 1)--arcs of G.

IsDistanceTransitive(G : parameters) : GrphUnd -> BoolElt

    Invariant: MonStgElt                Default: 

    Minlevel: RngIntElt                 Default: 0

    Maxlevel: RngIntElt                 Default: 

    Arg: RngIntElt                      Default: 

    IgnoreLabels: BoolElt               Default: false

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. The parameters are as in IsTransitive.

IsDistanceRegular(G) : GrphUnd -> BoolElt

Returns true if the graph G is distance regular, otherwise false.

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

• = number of vertices in N_(j - 1)(v) that are adjacent to u, (1 <= j <= d).
• = number of vertices in N_(j + 1)(v) that are adjacent to u (0 <= j <= d - 1).

Example Graph_AutomorphismGroup (H93E17)

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