[Next] [Prev] [_____] [Left] [Up] [Index] [Root]
Symmetry and Regularity Properties of Graphs
Symmetry and Regularity Properties of Graphs
IsTransitive(G) : GrphUnd -> BoolElt
IsVertexTransitive(G) : GrphUnd -> BoolElt
True if the automorphism group of the graph G is transitive, otherwise false.
IsEdgeTransitive(G) : GrphUnd -> BoolElt
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).
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.
IsPrimitive(G) : GrphUnd -> BoolElt
True if the graph G is primitive, i.e. if its automorphism group is
primitive.
IsSymmetric(G) : GrphUnd -> BoolElt
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.
[Future release] IsArcTransitive(G, t) : GrphUnd, RngIntElt -> BoolElt
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) : GrphUnd -> BoolElt
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.
IsDistanceRegular(G) : GrphUnd -> BoolElt
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 (H55E14)
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 ]
[Next] [Prev] [_____] [Left] [Up] [Index] [Root]