ADDITION.
On p. 346 insert an improved definition of complete regularity in
arbitrary graphs. Neumaier (cf.
.SC Brouwer
.[[
Brouwer 1990 completely regular codes note
.]])
showed that for distance-regular graphs this definition is
equivalent to the one given in \(sc11.1, and it is often
much easier to work with.
.LP
Let $GAM = (X,E)$ be a connected graph, and $C$ a subset of its
vertex set $X$. Then $C$ induces a partition
$PI (C) = "{"C sub 0 , ... , C sub t "}"$ of $X$, where
$C sub i = "{" x mo X vb d(x,C) = i "}"$, and
$t = t(C)$ is the covering radius of $C$.
We call $C$ \fIcompletely regular\fP when this partition
is regular in the sense of \(scA4 (p. 436), i.e.,
when there are numbers $a sub i$, $b sub i$, $c sub i$ $(0 <= i <= t)$
such that each $x mo C sub i$ has $a sub i$ neighbours in $C sub i$,
$b sub i$ neighbours in $C sub i+1$, and $c sub i$ neighbours in
$C sub i-1$. (Then necessarily $GAM$ is regular of valency
$k$, where $a sub i + b sub i + c sub i = k$ for all $i$.
Clearly $c sub 0 = b sub t = 0$.)
ADDITION.
On p. 348, line $-11$, insert `Clearly, every $s$-regular code
is $s$-uniform.'
CORRECTION.
On p. 348, line $-7$, change `$e sub il$' into `$e sub {l i}$'.
On line $-1$ change `$vb x sup perp ca C sub l vb$'
into `$vb GAM (x) ca C sub l vb$'.
ADDITION.
On p. 353 after Proposition 11.1.9, add the following
(essentially due to Bill Martin = wjmartiniii@violet.uwaterloo.ca,
email communication 1990).
.LP
.B
11.1.9A. Theorem.
.I
Let $GAM$ be a distance-regular graph with completely regular
partition $PI$, and $DEL = GAM / PI$ the corresponding quotient graph.
Let $pi : GAM arrow DEL$ be the quotient map.
.IP (i)
.I
If $C$ is a completely regular code in $DEL$, then
$pi sup -1 (C)$ is a completely regular code in $GAM$.
.IP (ii)
.I
If $SIGMA$ is a completely regular partition in $DEL$,
then $pi sup -1 SIGMA = "{" pi sup -1 C vb C mo SIGMA "}"$
is a completely regular partition in $GAM$, and
$GAM / pi sup -1 SIGMA isom DEL / SIGMA$.
.Eop
.LP
ADDITION.
On p. 354 at the end of Section 11.1C, add:
.LP
The following result shows that
Terwilliger's powerful diameter bound $Param$.2.2
is applicable to almost all translation distance-regular graphs.
.LP
$Le$
.SC (van Bon
.[[
van Bon thesis 1990 affine
.]]).
.I
Suppose $GAMMA$ is a translation distance-regular graph
but neither complete nor a conference graph. Then $GAM$
contains a quadrangle.
.LP
$Pf$. Let $X$ be the elementary abelian group of exponent $p$
(written additively) with which $V GAMMA$ can be identified. By Theorem
$CodeGr$.1.10 $s x mo GAM (0)$ whenever
$x mo GAM (0)$ and $s mo GF (p) sup \(** $.
Assume now that $GAMMA$ has no quadrangle.
Since $GAMMA$ is non-complete,
there are $x,y mo GAM (0)$ with $d (x,y) = 2$.
By induction on $i$ ($0 <= i <= p-1$) we show that $x+iy mo GAM (0)$.
Indeed, this is clear for $i = 0$, and if $x adj -iy$ then
$x , x+y , y , -iy , x$ is a 4-cycle, and since $GAM$
does not have induced quadrangles we have $x+y adj -iy$, i.e.,
$x + (i+1)y mo GAM (0)$. In particular we find for $i = p-1$
that $x-y mo GAM (0)$, contradiction.
.Eop
.Small
[Note that there are many Cayley graphs without quadrangles,
such as the graphs defined by the difference set
$D = "{" -a, -a+1, ... , -1, 1, ... , a-1, a "}"$ in $Zz sub m$
for $m >= 4a+1$.]
.Big
ADDITION.
On p. 355 add `$e$-error correcting' in line 10.
After line $-14$, add:
.LP
For $e = 1$ one knows that $(n,q,e) != (7,6,1)$ (R.E. Block & M. Hall, jr.,
.Ax "Block, R.E."
.Ax "Hall, M., jr."
.Ax "Roos, C."
cf.
.SC van Lint
.[[
Lint coding theory 1971
.]],
p. 87), and, e.g., $(n,q,e) != (19,6,1)$ [C. Roos].
[Indeed, Block & Hall showed that the existence of a
perfect code with $(n,q,e) = (7,6,1)$ would lead to
the existence of a pair of mutually orthogonal Latin squares of order 6
(and there is no such pair by
.SC Tarry
.[[
Tarry 1900
.]]).
More generally, Roos observed (around 1978?) that any 1-perfect code $C$
is an orthogonal array of strength $t := S/q - 1$, where
$S := 1 + (q-1)n$ is the volume of a ball of radius one,
(because $(aQ) sub j = 0$ for $j != 0,S/q$, so $C$ is a $t$-design
in the Hamming scheme). In particular it follows that
$q sup t$ divides $vb C vb = q sup n slash S$, i.e., $S vb q sup n-t$,
an improvement of the sphere-packing condition $S vb q sup n$.]
.SC Hong
.[[
Hong nonexistence perfect Hamming 1986
.]]
shows by a uniform proof that for $e >= 3$ and $q >= 3$ there are
no nontrivial perfect $e$-codes and no tight $2e$-designs in $H(n,q)$.
ADDITION.
On p. 355, line $-8$, replace the sentence `We don't know ... case (vi)'
by: `In case (vi), the partition
$"{"C + u vb wt u <= 1 "}"$ is completely regular. Indeed, more generally,
when $C$ is an $e$-error-correcting code, the partition
$"{"C + u vb wt u <= e "}"$ is completely regular'.
ADDITION.
On p. 356, line 6, add the references
.SC de Resmini
.[[
de Resmini 1987 set type
.]],
.SC de Resmini & Migliori
.[[
de Resmini Migliori 1986 set type
.]],
.SC de Lange
.[[
de Lange cyclotomic master's thesis 1990
.]]
and
.SC Gulliver
.[[
Gulliver optimal ternary strongly regular
.]].
SPELLING CORRECTION.
On p. 356, line $-3$, replace `BCD' by `BCH'.
ADDITION.
On p. 357, lines 1-2, add the answer: `In
.SC Brouwer
.[[
Brouwer completely regular note 1990
.]
.[
Brouwer complete regularity extended codes
.]]
it is shown that an even binary code is completely regular
if and only if all truncations of this
code are completely regular with the same parameters.
A result slightly weaker than the `if' part of this statement
was given by
.SC Sol\*'e
.[[
Sol\*('e completely regular transitive 1990
.]]).'
ADDITION.
On p. 357, after the second paragraph in \(sc11.1E,
add: `$S(5,8,24)$ is uniformly packed in $J(24,8)$
with $del = 4$, $r = 2$.'
ADDITION.
On p. 358, line 2, add: `For a completely regular partition
of the quadratic forms graphs with even $q$, see p. 293.
CORRECTION.
On p. 358, line 20, replace `Shortening' by `Truncating'.
SPELLING CORRECTION & ADDITIONS.
On p. 360, \(sc11.3B, line 3, change `cf' into `Cf'.
Add the information that the Berlekamp-van Lint-Seidel graph
has full automorphism group $3 sup 5 . 2 . M sub 11$.
The problem has been solved by Koolen & Riebeek, who constructed
a graph with intersection array $"{"45,44,36,5;1,9,40,45"}"$
and automorphism group $3 sup 5 : (2 times M sub 10 )$.
ADDITION.
On p. 360, \(sc11.3C, add: `This graph is uniquely determined
by its parameters and has full automorphism group
$3 sup 4 .( 2 times Sym (6) ). 2$
.SC (Brouwer & Haemers
.[[
Brouwer Haemers uniqueness strongly regular 1992
.]]).'
CORRECTION.
On p. 361, line $-17$, change `11.2.2' into `11.3.2'.
ADDITION.
On p. 365 (and on p. 213 in Table 6.10) add the information
that the five graphs (A14)-(A18) are distance-transitive with
automorphism groups $2 sup 11 . M sub 22$, $2 sup 10 . PSIGL (3,4)$,
$2 sup 11 . PGAML (3,4)$, $3 sup 5 . 2 . M sub 10$ and
$3 sup 6 . 2 . M sub 11$, respectively.
ADDITION.
On p. 368, in the remark, replace `it is unknown whether such graphs exist'
by `however,
.SC Ivanov & Shpectorov
.[[
Ivanov Shpectorov geometry nontrivial coverings
.]]
showed that no such graphs exist'.
ADDITION.
On p. 371, add at the end of Section 11.4F: In
.SC Brouwer
.[[
Brouwer 1983 uniqueness regular thin near octagon
.]]
also other bipartite graphs with $c sub 2 = 2$, $c sub 3 = 5$
are discussed, and, in particular, the nonexistence of graphs
.Ia 4 164 "%10,9,8,5;1,2,5,10%"
with intersection array $"{"10,9,8,5;1,2,5,10"}"$ is shown.
CORRECTION.
On p. 373, line 17, instead of the parameters of $LAM sub 2 ( lam )$,
those of its complement were given. Replace `(162,105,72,60)'
by `(162,56,10,24)'.
ADDITION.
On p. 373 add new sections 11.4I and 11.4J.
.Na "I" "The Soicher graph - an antipodal 3-cover of the second \
subconstituent of the McLaughlin graph"
The second subconstituent $GAM$ of the McLaughlin graph $LAM$ on 275 vertices
is strongly regular with parameters $(v,k, lam , mu ) = (162,56,10,24)$,
and is the unique graph with these parameters
.SC (Cameron, Goethals & Seidel
.[[
Cameron Goethals Seidel 1978 subconstituents
.]]).
Let us give an explicit description of this graph:
.LP
Take as vertices a symbol $inf$, the 56 hyperovals in $PG(2,4)$ in
a single $L sub 3 (4)$-orbit, and the 105 flags of $PG(2,4)$.
Let $inf$ be adjacent to the hyperovals, let two hyperovals be adjacent
when they are disjoint, let $(p,L) adj O$ when
$vb O ca L minus "{"p"}" vb = 2$ and let $(p,L) adj (q,M)$ when
$p != q$ and $L != M$ and $(p mo M ~ roman "or" ~ q mo L)$.
.LP
Now we find on the hyperovals the strongly regular Gewirtz graph
with parameters $(v,k, lam , mu ) = (56,10,0,2)$ and on the flags
a strongly regular graph with parameters $(v,k, lam , mu ) = (105,32,4,12)$
as is well-known and easily checked; using this it quickly follows
that the graph $GAM$ just constructed is strongly regular with the
stated parameters, and hence is isomorphic to the second subconstituent
of the McLaughlin graph.
.LP
The automorphism groups (given in $Atlas$
.[[
Conway Parker Norton Atlas
.]]
notation) of these graphs are as follows. The graph $LAM$ has
automorphism group $McL . 2$ with point stabilizer $U sub 4 (3):2 sub 3$.
The graph $GAM$ has automorphism group $U sub 4 (3) : (2 sup 2 ) sub 133$
with point stabilizer $L sub 3 (4) : 2 sup 2$.
Its subconstituents have automorphism group $L sub 3 (4) : 2 sup 2$
with point stabilizers $A sub 6 cdot 2 sup 2$ and
$2 sup 2+4 . 3 . 2 sup 2$, respectively.
All these graphs are distance-transitive, except the graph on 105 vertices,
which has rank 4.
.B
11.4.6. Theorem.
.I
There is a unique distance-regular graph $DEL$ with intersection array
$"{"56,45,16,1;1,8,45,56"}"$ and distance distribution diagram
.so diag/diag486
and no other antipodal covers of $GAM$ exist, that is, there
do not exist distance-regular graphs with intersection array
$"{"56,45,12,1;1,12,45,56"}"$ or
$"{"56,45,18,1;1,6,45,56"}"$ or
$"{"56,45,20,1;1,4,45,56"}"$ or
$"{"56,45,21,1;1,3,45,56"}"$.
The graph $DEL$ is distance-transitive with automorphism group
$3 . U sub 4 (3) : 2 sup 2$ and point stabilizer
$L sub 3 (4) : 2 sup 2$.
.LP
.B Proof.
In $GAM$ the $mu$-graphs (the graphs induced on the common neighbours
of two nonadjacent vertices) are isomorphic to $6K sub 2,2$
(the disjoint union of six quadrangles), and if
$M = gam sup perp ca del sup perp$ is such a $mu$-graph, then each
neighbour of $gam$ not in $M$ has a unique neighbour in each of the
six connected components of $M$.
.LP
The parameters for a distance-regular antipodal $r$-cover of $GAM$
are feasible for $r mo "{"2,3,4,6,8"}"$, but clearly the $mu$-graphs
of a cover are unions of connected components of the $mu$-graph of
$GAM$, so $r mo "{"4,8"}"$ does not occur.
We show that only $r = 3$ occurs, even without assuming
distance-regularity.
.LP
Fix a base point $inf$, and consider the homotopy group of closed paths
in $GAM$ starting at $inf$, modulo all triangles in $GAM$. Using the
mentioned property of $mu$-graphs (and the fact that the second
subconstituent of a nontrivial strongly regular graph is connected)
one finds that each closed path is homotopic (modulo triangles)
to a quadrangle $inf adj alpha sub i adj beta adj gam sub j adj inf$
where $beta$ is a fixed vertex at distance two from $inf$.
This shows that the universal cover (among the covers that are locally
isomorphisms) is finite, and a small computer program shows that in fact
this universal cover is a 3-cover.
.Eop
It is amusing to remark that $GAM$ and $DEL$ have Buekenhout diagram
.so ! Buekdiag 3 4 "\(sb" / 1 points / 1 edges / 1 triangles / 8 octahedra / .
The graph $DEL$ was discovered by
.SC Soicher
.[[
Soicher distance-regular graphs 1993
.]].
He also observed the following.
.B
11.4.7 Theorem
.R
.SC (Soicher
.[[
Soicher distance-regular graphs 1993
.]]).
.I
The second subconstituent $roman E$ of $DEL$ is itself distance-regular
with intersection array $"{"32,27,8,1;1,4,27,32"}"$ and
distance-distribution diagram
.so diag/diag315s
an antipodal 3-cover of the Goethals-Seidel graph (on the 105 flags
of $PG(2,4)$).
$Aut ( roman E ) isom (3 times L sub 3 (4)) : 2 sup 2$, acting rank 6,
with point stabilizer $Alt (6) cdot 2 sup 2$.
.Eop
.R
The Goethals-Seidel graph is strongly regular of rank 6,
so $roman E$ is not distance-transitive; in fact the subconstituent
of size 216 splits into two suborbits, of sizes 24 and 192, respectively.
The graph induced on the suborbit of size 24 is $3K sub 4,4$.
.Na "I" "Another Soicher graph - z
CORRECTION & ADDITION.
In \(sc11.5 on p. 373, line $-3$ it is stated that the incidence
graph $DEL$ of the van Lint-Schrijver partial geometry is
distance-transitive, but it is not. Replace this line by the following text.
We have $Aut DEL isom 3 sup 4 . ( Sym (6) times 2 )$, with permutation
rank 7 on $DEL$. The halved graph $E$ of $DEL$ (a strongly regular graph
with parameters $(v,k, lam , mu ) = (81,30,9,12)$)
.Ia 2 81 "%30,20;1,12%"
has full group of automorphisms $3 sup 4 . Sym (6)$ with permutation rank 4.
.sp 0.4
.Small
[The graph $E$ is the graph on $bold 1 sup perp / bold 1$ where
$gam adj del$ when $Q( gam - del ) = 2$, where
$Q((x sub 1 , ... , x sub 6 )) = sum x sub i supr(2)$.
This shows that construction FE4 of
.SC Calderbank & Kantor
.[[
Calderbank Kantor geometry two-weight codes 1986
.]]
is a special case of their construction FE1.]
$DEL sub 3 ( gam )$ and $DEL sub 4 ( gam )$ split into orbits
of sizes 60, 15 and 20, 30 (respectively) for the stabilizer of $gam$.
D. Pasechnik observed that if $R sub 3B$ and $R sub 4B$ are the
relations corresponding to these suborbits of sizes 15 and 30,
then $R sub 3B cu R sub 4B$ defines on the vertex set of $DEL$
a graph that is locally $GQ(4,2)$.
This latter graph is an induced subgraph of the $U sub 6 (2)$
polar graph.
.Big