/usr/share/gap/pkg/grape/htm/CHAP004.htm is in gap-grape 4r7+ds-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 | <html><head><title>[grape] 4 Functions to determine regularity properties of graphs</title></head>
<body text="#000000" bgcolor="#ffffff">
[<a href = "chapters.htm">Up</a>] [<a href ="CHAP003.htm">Previous</a>] [<a href ="CHAP005.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<h1>4 Functions to determine regularity properties of graphs</h1><p>
<P>
<H3>Sections</H3>
<oL>
<li> <A HREF="CHAP004.htm#SECT001">IsRegularGraph</a>
<li> <A HREF="CHAP004.htm#SECT002">LocalParameters</a>
<li> <A HREF="CHAP004.htm#SECT003">GlobalParameters</a>
<li> <A HREF="CHAP004.htm#SECT004">IsDistanceRegular</a>
<li> <A HREF="CHAP004.htm#SECT005">CollapsedAdjacencyMat</a>
<li> <A HREF="CHAP004.htm#SECT006">OrbitalGraphColadjMats</a>
<li> <A HREF="CHAP004.htm#SECT007">VertexTransitiveDRGs</a>
</ol><p>
<p>
This chapter describes functions to determine regularity properties of
graphs, and a function <code>VertexTransitiveDRGs</code> which determines the
distance-regular graphs on which a given transitive permutation group
acts as a vertex-transitive group of automorphisms.
<p>
<p>
<h2><a name="SECT001">4.1 IsRegularGraph</a></h2>
<p><p>
<a name = "SSEC001.1"></a>
<li><code>IsRegularGraph( </code><var>gamma</var><code> )</code>
<p>
This boolean function returns <code>true</code> if and only if the graph <var>gamma</var> is
(out)regular.
<p>
<pre>
gap> IsRegularGraph( JohnsonGraph(4,2) );
true
gap> IsRegularGraph( EdgeOrbitsGraph(Group(()),[[1,2]],2) );
false
</pre>
<p>
<p>
<h2><a name="SECT002">4.2 LocalParameters</a></h2>
<p><p>
<a name = "SSEC002.1"></a>
<li><code>LocalParameters( </code><var>gamma</var><code>, </code><var>V</var><code> )</code>
<li><code>LocalParameters( </code><var>gamma</var><code>, </code><var>V</var><code>, </code><var>G</var><code> )</code>
<p>
Let <var>gamma</var> be a simple connected graph. Then this function determines
all local parameters <i>c</i><sub><i>i</i></sub>(<i>V</i> ), <i>a</i><sub><i>i</i></sub>(<i>V</i> ), and <i>b</i><sub><i>i</i></sub>(<i>V</i> ) that <var>gamma</var>
may have, with respect to the singleton vertex or nonempty list of
vertices <var>V</var>. We say that <var>gamma</var> has the <strong>local parameter</strong> <i>c</i><sub><i>i</i></sub>(<i>V</i>)
(respectively <i>a</i><sub><i>i</i></sub>(<i>V</i>), <i>b</i><sub><i>i</i></sub>(<i>V</i>)), with respect to <i>V</i>, if the number
of vertices at distance <i>i</i>−1 (respectively <i>i</i>, <i>i</i>+1) from <i>V</i> that
are adjacent to a vertex <i>w</i> at distance <i>i</i> from <i>V</i> (see <a href="CHAP003.htm#SSEC015.1">Distance</a>)
is the constant <i>c</i><sub><i>i</i></sub>(<i>V</i>) (respectively <i>a</i><sub><i>i</i></sub>(<i>V</i>), <i>b</i><sub><i>i</i></sub>(<i>V</i>)) depending
only on <i>i</i> and <i>V</i> (and not <i>w</i>).
<p>
The function <code>LocalParameters</code> returns a list whose <i>i</i>-th element is
the list [<i>c</i><sub><i>i</i>−1</sub>(<i>V</i> ), <i>a</i><sub><i>i</i>−1</sub>(<i>V</i> ), <i>b</i><sub><i>i</i>−1</sub>(<i>V</i> )], except that if
some local parameter does not exist then −1 is put in its place.
<p>
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.
<p>
The optional parameter <var>G</var>, if present, is assumed to be a subgroup of
\Aut(<i>gamma</i> ) fixing <var>V</var> setwise. Including such a <var>G</var> can speed up
the function.
<p>
<pre>
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 ] ]
</pre>
<p>
<p>
<h2><a name="SECT003">4.3 GlobalParameters</a></h2>
<p><p>
<a name = "SSEC003.1"></a>
<li><code>GlobalParameters( </code><var>gamma</var><code> )</code>
<p>
Let <var>gamma</var> be a simple connected graph, and 0 ≤ <i>i</i> ≤ <tt>Diameter</tt><tt>(</tt><i>gamma</i> <tt>)</tt>. This function determines all global parameters
<i>c</i><sub><i>i</i></sub>, <i>a</i><sub><i>i</i></sub>, and <i>b</i><sub><i>i</i></sub> that <var>gamma</var> may have. We say that <var>gamma</var> has
the <strong>global parameter</strong> <i>c</i><sub><i>i</i></sub> (respectively <i>a</i><sub><i>i</i></sub>, <i>b</i><sub><i>i</i></sub>) if the number
of vertices at distance <i>i</i>−1 (respectively <i>i</i>, <i>i</i>+1) from a vertex
<i>v</i> that are adjacent to a vertex <i>w</i> at distance <i>i</i> from <i>v</i> is the
constant <i>c</i><sub><i>i</i></sub> (respectively <i>a</i><sub><i>i</i></sub>, <i>b</i><sub><i>i</i></sub>) depending only on <i>i</i> (and
not <i>v</i> and <i>w</i>).
<p>
The function <code>GlobalParameters</code> returns a list of length
<code>Diameter</code>(<var>gamma</var>)+1, whose <i>i</i>-th element is the list [<i>c</i><sub><i>i</i>−1</sub>, <i>a</i><sub><i>i</i>−1</sub>, <i>b</i><sub><i>i</i>−1</sub>], except that if some global parameter does not exist
then −1 is put in its place.
<p>
Note that <var>gamma</var> is <strong>distance-regular</strong> if and only if this function
returns no −1 in place of a global parameter (see <a href="biblio.htm#BCN89"><cite>BCN89</cite></a>).
<p>
See also <a href="CHAP004.htm#SSEC002.1">LocalParameters</a> and <a href="CHAP004.htm#SSEC004.1">IsDistanceRegular</a>.
<p>
<pre>
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 ] ]
</pre>
<p>
<p>
<h2><a name="SECT004">4.4 IsDistanceRegular</a></h2>
<p><p>
<a name = "SSEC004.1"></a>
<li><code>IsDistanceRegular( </code><var>gamma</var><code> )</code>
<p>
This boolean function returns <code>true</code> if and only if <var>gamma</var> is
<strong>distance-regular</strong>, i.e. <var>gamma</var> is simple, connected, and all global
parameters <i>c</i><sub><i>i</i></sub>,<i>a</i><sub><i>i</i></sub>,<i>b</i><sub><i>i</i></sub> exist for 0 ≤ <i>i</i> ≤ <tt>Diameter</tt><tt>(</tt><i>gamma</i> <tt>)</tt>
(see <a href="biblio.htm#BCN89"><cite>BCN89</cite></a>).
<p>
See also <a href="CHAP004.htm#SSEC003.1">GlobalParameters</a>.
<p>
<pre>
gap> gamma := JohnsonGraph(4,2);;
gap> IsDistanceRegular( gamma );
true
gap> IsDistanceRegular( BipartiteDouble(gamma) );
false
</pre>
<p>
<p>
<h2><a name="SECT005">4.5 CollapsedAdjacencyMat</a></h2>
<p><p>
<a name = "SSEC005.1"></a>
<li><code>CollapsedAdjacencyMat( </code><var>gamma</var><code> )</code>
<li><code>CollapsedAdjacencyMat( </code><var>G</var><code>, </code><var>gamma</var><code> )</code>
<p>
The second form of this function returns the collapsed adjacency
matrix for <var>gamma</var>, where the collapsing group is <var>G</var>. It is
assumed that <var>G</var> is a subgroup of \Aut(<i>gamma</i> ).
<p>
The (<i>i</i>,<i>j</i>)-entry of the collapsed adjacency matrix equals the number of
edges in { [<i>x</i>,<i>y</i>] | <i>y</i> ∈ <i>j</i>-th <var>G</var>-orbit}, where <i>x</i> is a fixed
vertex in the <i>i</i>-th <var>G</var>-orbit.
<p>
In the case where this function is given just one argument, then it must
be a graph <var>gamma</var> with the property that <code></code><var>gamma</var><code>.group</code> is transitive on
the vertex-set of <var>gamma</var>. In this case, the returned collapsed adjacency
matrix for <var>gamma</var> is with respect to the stabilizer in <code></code><var>gamma</var><code>.group</code>
of 1.
<p>
The reader is warned that collapsed adjacency matrices can have different,
but related meanings depending on the setting and the author.
<p>
See also <a href="CHAP004.htm#SSEC006.1">OrbitalGraphColadjMats</a>.
<p>
<pre>
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 ] ]
</pre>
<p>
<p>
<h2><a name="SECT006">4.6 OrbitalGraphColadjMats</a></h2>
<p><p>
<a name = "SSEC006.1"></a>
<li><code>OrbitalGraphColadjMats( </code><var>G</var><code> )</code>
<li><code>OrbitalGraphColadjMats( </code><var>G</var><code>, </code><var>H</var><code> )</code>
<p>
This function returns a list of collapsed adjacency matrices for the
orbital digraphs of the transitive permutation group <var>G</var>, collapsed
with respect to <code>Stabilizer(</code><var>G</var><code>,1)</code> (creating collapsed adjacency
matrices for the orbital digraphs in the sense of <a href="biblio.htm#PS97"><cite>PS97</cite></a>). Also,
the matrices are collapsed with respect to a fixed ordering of the
orbits of <code>Stabilizer(</code><var>G</var><code>,1)</code>, with the trivial orbit <code>[1]</code> coming
first.
<p>
The optional parameter <var>H</var>, if included, should be equal to
<code>Stabilizer(</code><var>G</var><code>,1)</code>. The knowledge of this stabilizer can speed up the
function.
<p>
The reader is warned that collapsed adjacency matrices can have different,
but related meanings depending on the setting and the author.
<p>
See also <a href="CHAP004.htm#SSEC005.1">CollapsedAdjacencyMat</a>.
<p>
<pre>
gap> OrbitalGraphColadjMats( SymmetricGroup(7) );
[ [ [ 1, 0 ], [ 0, 1 ] ], [ [ 0, 6 ], [ 1, 5 ] ] ]
</pre>
<p>
<p>
<h2><a name="SECT007">4.7 VertexTransitiveDRGs</a></h2>
<p><p>
<a name = "SSEC007.1"></a>
<li><code>VertexTransitiveDRGs( </code><var>coladjmats</var><code> )</code>
<li><code>VertexTransitiveDRGs( </code><var>G</var><code> )</code>
<p>
This function can determine (among other things) all the
distance-regular graphs on which a given transitive permutation group
<var>G</var> acts as a vertex-transitive group of automorphisms (as long as the
permutation rank of <var>G</var> is not too large).
<p>
In the first form of this function, the input parameter <var>coladjmats</var>
must be a list of collapsed adjacency matrices for the orbital digraphs
of some transitive permutation group <var>G</var>, collapsed with respect to a
point stabilizer (such as the list of matrices produced by the function
<code>OrbitalGraphColadjMats</code>). 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,
<code></code><var>coladjmats</var><code>[1]</code> must be an identity matrix.
<p>
In the second form of this function, the input parameter <var>G</var> must be a
transitive permutation group, and then the result returned will be
the same as <code>VertexTransitiveDRGs( OrbitalGraphColadjMats( </code><var>G</var><code> ) )</code>.
<p>
In either case, this function returns a record <var>result</var>, which gives
information on the transitive group <var>G</var> acting on its natural set <i>V</i>.
The most important component of this record is the list
<code>orbitalCombinations</code>, whose elements give the sets of (the indices of)
the <var>G</var>-orbitals whose union gives the edge-set of a distance-regular
graph with vertex-set <i>V</i>. The component <code>intersectionArrays</code> gives the
corresponding intersection arrays. The component <code>degree</code> is the degree
of the permutation group <var>G</var>, <code>rank</code> is its (permutation) rank, and
<code>isPrimitive</code> is true if <var>G</var> is primitive, and <code>false</code> otherwise.
<p>
The techniques used in this function and definitions of the terms used
above can be found in <a href="biblio.htm#PS97"><cite>PS97</cite></a>.
<p>
<strong>Warning</strong> This function checks all subsets of <code>[2..</code><var>result</var><code>.rank]</code>, so
the permutation rank of <var>G</var> must not be large!
<p>
<pre>
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 ] ] ] )
</pre>
<p>
[<a href = "chapters.htm">Up</a>] [<a href ="CHAP003.htm">Previous</a>] [<a href ="CHAP005.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<P>
<address>grape manual<br>January 2016 (Debian 4r7+ds-3)
</address></body></html>
|