This chapter describes functions to determine regularity properties of
graphs, and a function VertexTransitiveDRGs
which determines the
distance-regular graphs on which a given transitive permutation group
acts as a vertex-transitive group of automorphisms.
IsRegularGraph(
gamma )
This boolean function returns true
if and only if the graph gamma is
(out)regular.
gap> IsRegularGraph( JohnsonGraph(4,2) ); true gap> IsRegularGraph( EdgeOrbitsGraph(Group(()),[[1,2]],2) ); false
LocalParameters(
gamma,
V )
LocalParameters(
gamma,
V,
G )
Let gamma be a simple connected graph. Then this function determines all local parameters ci(V ), ai(V ), and bi(V ) that gamma may have, with respect to the singleton vertex or nonempty list of vertices V. We say that gamma has the local parameter ci(V) (respectively ai(V), bi(V)), with respect to V, if the number of vertices at distance i-1 (respectively i, i+1) from V that are adjacent to a vertex w at distance i from V (see Distance) is the constant ci(V) (respectively ai(V), bi(V)) depending only on i and V (and not w).
The function LocalParameters
returns a list whose i-th element is
the list [ci-1(V ), ai-1(V ), bi-1(V )], except that if
some local parameter does not exist then -1 is put in its place.
This function can be used to determine whether a given subset of the vertices of a graph is a distance-regular code in that graph.
The optional parameter G, if present, is assumed to be a subgroup of \Aut(gamma ) fixing V setwise. Including such a G can speed up the function.
gap> gamma := JohnsonGraph(4,2);; gap> LocalParameters( gamma, 1 ); [ [ 0, 0, 4 ], [ 1, 2, 1 ], [ 4, 0, 0 ] ] gap> LocalParameters( gamma, [1,6] ); [ [ 0, 0, 4 ], [ 2, 2, 0 ] ] gap> LocalParameters( gamma, [1,2] ); [ [ 0, 1, 3 ], [ -1, -1, 0 ] ]
GlobalParameters(
gamma )
Let gamma be a simple connected graph, and 0 £ i £ Diameter(gamma ). This function determines all global parameters ci, ai, and bi that gamma may have. We say that gamma has the global parameter ci (respectively ai, bi) if the number of vertices at distance i-1 (respectively i, i+1) from a vertex v that are adjacent to a vertex w at distance i from v is the constant ci (respectively ai, bi) depending only on i (and not v and w).
The function GlobalParameters
returns a list of length
Diameter
(gamma)+1, whose i-th element is the list [ci-1, ai-1, bi-1], except that if some global parameter does not exist
then -1 is put in its place.
Note that gamma is distance-regular if and only if this function returns no -1 in place of a global parameter (see BCN89).
See also LocalParameters and IsDistanceRegular.
gap> gamma := JohnsonGraph(4,2);; gap> GlobalParameters( gamma ); [ [ 0, 0, 4 ], [ 1, 2, 1 ], [ 4, 0, 0 ] ] gap> GlobalParameters( BipartiteDouble(gamma) ); [ [ 0, 0, 4 ], [ 1, 0, 3 ], [ -1, 0, -1 ], [ 4, 0, 0 ] ]
IsDistanceRegular(
gamma )
This boolean function returns true
if and only if gamma is
distance-regular, i.e. gamma is simple, connected, and all global
parameters ci,ai,bi exist for 0 £ i £ Diameter(gamma )
(see BCN89).
See also GlobalParameters.
gap> gamma := JohnsonGraph(4,2);; gap> IsDistanceRegular( gamma ); true gap> IsDistanceRegular( BipartiteDouble(gamma) ); false
CollapsedAdjacencyMat(
gamma )
CollapsedAdjacencyMat(
G,
gamma )
The second form of this function returns the collapsed adjacency matrix for gamma, where the collapsing group is G. It is assumed that G is a subgroup of \Aut(gamma ).
The (i,j)-entry of the collapsed adjacency matrix equals the number of edges in { [x,y] | y Î j-th G-orbit}, where x is a fixed vertex in the i-th G-orbit.
In the case where this function is given just one argument, then it must
be a graph gamma with the property that gamma
.group
is transitive on
the vertex-set of gamma. In this case, the returned collapsed adjacency
matrix for gamma is with respect to the stabilizer in gamma
.group
of 1.
See also OrbitalGraphColadjMats.
gap> gamma := JohnsonGraph(4,2); rec( isGraph := true, order := 6, group := Group([ (1,4,6,3)(2,5), (2,4)(3,5) ]), schreierVector := [ -1, 2, 1, 1, 1, 1 ], adjacencies := [ [ 2, 3, 4, 5 ] ], representatives := [ 1 ], names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ], isSimple := true ) gap> G := Stabilizer( gamma.group, [1,6], OnSets );; gap> CollapsedAdjacencyMat( G, gamma ); [ [ 0, 4 ], [ 2, 2 ] ] gap> CollapsedAdjacencyMat( gamma ); [ [ 0, 4, 0 ], [ 1, 2, 1 ], [ 0, 4, 0 ] ]
OrbitalGraphColadjMats(
G )
OrbitalGraphColadjMats(
G,
H )
This function returns a list of collapsed adjacency matrices for the
orbital digraphs of the transitive permutation group G, collapsed
with respect to Stabilizer(
G,1)
(creating collapsed adjacency
matrices for the orbital digraphs in the sense of PS97). Also,
the matrices are collapsed with respect to a fixed ordering of the
orbits of Stabilizer(
G,1)
, with the trivial orbit [1]
coming
first.
The optional parameter H, if included, should be equal to
Stabilizer(
G,1)
. The knowledge of this stabilizer can speed up the
function.
For backward compatibility, an alternative name for this function is
OrbitalGraphIntersectionMatrices
indexOrbitalGraphIntersectionMatrices,
but the reader is warned that intersection matrices (and even collapsed
adjacency matrices) can have different, but closely related meanings
depending on the setting and the author. See, for example, Cam99.
See also CollapsedAdjacencyMat.
gap> OrbitalGraphColadjMats( SymmetricGroup(7) ); [ [ [ 1, 0 ], [ 0, 1 ] ], [ [ 0, 6 ], [ 1, 5 ] ] ]
VertexTransitiveDRGs(
coladjmats )
VertexTransitiveDRGs(
G )
This function can determine (among other things) all the distance-regular graphs on which a given transitive permutation group G acts as a vertex-transitive group of automorphisms (as long as the permutation rank of G is not too large).
In the first form of this function, the input parameter coladjmats
must be a list of collapsed adjacency matrices for the orbital digraphs
of some transitive permutation group G, collapsed with respect to a
point stabilizer (such as the list of matrices produced by the function
OrbitalGraphColadjMats
). It is assumed that the orbital/suborbit
indexing used is the same as that for the rows (and columns) of each of
the matrices, as well as for the indexing of the matrices themselves,
with the trivial orbital first, so that, in particular,
coladjmats
[1]
must be an identity matrix.
In the second form of this function, the input parameter G must be a
transitive permutation group, and then the result returned will be
the same as VertexTransitiveDRGs( OrbitalGraphColadjMats(
G ) )
.
In either case, this function returns a record result, which gives
information on the transitive group G acting on its natural set V.
The most important component of this record is the list
orbitalCombinations
, whose elements give the sets of (the indices of)
the G-orbitals whose union gives the edge-set of a distance-regular
graph with vertex-set V. The component intersectionArrays
gives the
corresponding intersection arrays. The component degree
is the degree
of the permutation group G, rank
is its (permutation) rank, and
isPrimitive
is true if G is primitive, and false
otherwise.
The techniques used in this function and definitions of the terms used above can be found in PS97.
Warning This function checks all subsets of [2..
result.rank]
, so
the permutation rank of G must not be large!
gap> m22:=PrimitiveGroup(22,1);; gap> syl:=SylowSubgroup(m22,11);; gap> part:=Set(Orbit(syl,1));; gap> l211:=Stabilizer(m22,part,OnSets);; gap> rt:=RightTransversal(m22,l211);; gap> m22big:=Action(m22,rt,OnRight);; gap> v:=VertexTransitiveDRGs(m22big); rec( degree := 672, rank := 6, isPrimitive := true, orbitalCombinations := [ [ 2, 3, 4, 5, 6 ], [ 2, 4 ], [ 3, 5, 6 ], [ 3, 6 ] ], intersectionArrays := [ [ [ 0, 0, 671 ], [ 1, 670, 0 ] ], [ [ 0, 0, 495 ], [ 1, 366, 128 ], [ 360, 135, 0 ] ], [ [ 0, 0, 176 ], [ 1, 40, 135 ], [ 48, 128, 0 ] ], [ [ 0, 0, 110 ], [ 1, 28, 81 ], [ 18, 80, 12 ], [ 90, 20, 0 ] ] ] )
[Up] [Previous] [Next] [Index]
GRAPE manual