\Chapter{Functions to determine regularity properties of graphs}
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.
Let <gamma> be a simple connected graph. Then this function determines
all local parameters $c_i(<V>)$, $a_i(<V>)$, and $b_i(<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* $c_i(V)$
(respectively $a_i(V)$, $b_i(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 $c_i(V)$ (respectively $a_i(V)$, $b_i(V)$) depending
only on $i$ and $V$ (and not $w$).
The function `LocalParameters' returns a list whose $i$-th element is
the list $[c_{i-1}(<V>), a_{i-1}(<V>), b_{i-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.
Let <gamma> be a simple connected graph, and $0 \le i \le
`Diameter(<gamma>)'$. This function determines all global parameters
$c_i$, $a_i$, and $b_i$ that <gamma> may have. We say that <gamma> has
the *global parameter* $c_i$ (respectively $a_i$, $b_i$) 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 $c_i$ (respectively $a_i$, $b_i$) depending only on $i$ (and
not $v$ and $w$).
The function `GlobalParameters' returns a list of length
`Diameter'()+1, whose $i$-th element is the list $[c_{i-1},
a_{i-1}, b_{i-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 \cite{BCN89}).
See also "LocalParameters" and "IsDistanceRegular".
This boolean function returns `true' if and only if is
*distance-regular*, i.e. <gamma> is simple, connected, and all global
parameters $c_i,a_i,b_i$ exist for $0 \le i \le `Diameter(<gamma>)'$
(see \cite{BCN89}).
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]\mid y \in 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.
The reader is warned that collapsed adjacency matrices can have different,
but related meanings depending on the setting and the author.
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 \cite{PS97}. These matrices are
given with respect to some ordering of the orbits of `Stabilizer(<G>,1)'
(the *suborbits*), with the trivial suborbit `[1]' coming first, and
with the $k$-th matrix corresponding to the orbital digraph having the
$k$-th suborbit as the adjacency of the vertex~1. The $(i,j)$-entry of the
$k$-th matrix in the returned list equals the number of (directed) edges
of the $k$-th orbital digraph that are in
$\{ [x,y]\mid y \in j$-th~suborbit$\}$,
where $x$ is a fixed vertex in the $i$-th suborbit.
The optional parameter <H>, if included, should be equal to
`Stabilizer(<G>,1)'. The knowledge of this stabilizer may speed up the
function.
Prior to {\GRAPE}~4.9.0 this function was called `OrbitalGraphColadjMats',
and for backward compatibility, this name will still work.
The reader is warned that collapsed adjacency matrices can have different,
but related meanings depending on the setting and the author. Note also
that the $k$-th *intersection matrix* for the coherent configuration
defined by <G> is the transpose of the collapsed adjacency matrix
corresponding to the suborbit paired with the suborbit defining the
$k$-th collapsed adjacency matrix for <G>. See Chapter 3 of \cite{Cam99}.
This function can determine (among other things) all the distance-regular
graphs on which a given non-trivial 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
non-trivial transitive permutation group <G>, collapsed with respect to a
fixed point-stabilizer (such as the list of matrices produced by the function
`OrbitalDigraphColadjMats'). 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
non-trivial transitive permutation group, and then the result returned
will be the same as `VertexTransitiveDRGs( OrbitalDigraphColadjMats( <G>
) )'.
In either case, this function returns a record <result>, which gives
information on the non-trivial 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 is primitive, and `false' otherwise.
The techniques used in this function and definitions of the terms used
above can be found in \cite{PS97}.
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
