ADDITION.
On p. 4, line 20, add:
.SC `Coolsaet
.[[
Coolsaet local structure
.]]
remarks that a connected graph satisfying R1 and R2 with $lam = mu = 2$
is regular.'
ADDITION.
On p. 5, line $-7$, add: `For locally co-Heawood graphs, see
.SC Brouwer, Fon-der-Flaass & Shpectorov
.[[
Brouwer Fon-der-Flaass Shpectorov 1993
.]].'
ADDITION.
On p. 8, after Corollary 1.2.4, add: `For example, no
distance-regular graph with parameters
$"{"28,15,9,1;1,3,15,28"}"$ ($v = 256$) does exist.'
HISTORICAL CORRECTION.
On p. 10, line 4, change the reference to `(cf.
.SC Belevitch
.[[
Belevitch 1950
.]]
and
.SC Wallis, Street & Wallis
.[[
Wallis Street
.]],
p. 293)'.
On line 12, change the reference to
.SC `(Raghavarao
.[[
Raghavarao 1960 aspects weighing
.]],
cf.
.SC Belevitch
.[[
Belevitch 1965 1968
.]],
.SC van Lint & Seidel
.[[
Lint Seidel equilateral 1966
.]])'.
HISTORICAL CORRECTION & ADDITION.
On p. 11, after the proof of Proposition 1.3.2, add the following
remark.
.LP
Proposition 1.3.2 is due to Delsarte (cf.
.[[
Delsarte approach 1973
.]],
p. 31) in the strongly regular case,
and was generalized by Hoffman
to regular graphs (see Proposition 3.7.2) and by Haemers (cf.
.[[
Haemers thesis 1979
.]],
\(sc2.1) to arbitrary graphs.
(See also
.SC Cvetkovi\*'c, Doob & Sachs
.[[
Cvetkovi\*'c Doob Sachs spectra 1979
.]],
p. 115.)
.SC Hoffman
.[[
Hoffman eigenvalues and colourings 1970
.]]
does not contain the upper bound $vb C vb <= 1 + M slash m$
for the size of cliques $C$, but the lower bound
$chi >= 1 + M slash m$ for the chromatic number of a graph
with largest eigenvalue $M$ and smallest eigenvalue $-m$.
.br
For cliques of size $c$ in edge-regular graphs Neumaier gave the
inequality $c sup 2 (v-2k+ lam ) + c(k sup 2 +3k- ( lam +2)v - lam )
- v(k- lam -1) <= 0$ with equality iff each vertex outside the clique
has a constant number of neighbours inside. This is just the
inequality $0 <= (v(k- mu ) + (v mu + mu - k - k sup 2 ) c
- mu c sup 2 ) c / (v - c)$ from the proof above applied to the
complementary graph.
SPELLING CORRECTION.
On p. 14, line $-4$, change `consist' into `consists'.
ADDITION.
On p. 16, strengthen Theorem 1.5.6 as follows.
.LP
.B
1.5.6. Theorem.
.I
Let $DEL$ be a strongly regular graph with parameters
$(v,k, lambda , mu )$. Then the two-graph $fs D = fs D ( DEL )$ is
regular if and only if $v = 2 ( 2k - lam - mu )$.
If this is the case, then $fs D sub inf$ is strongly regular
with parameters $(v - 1, 2(k - mu ), k + lam - 2 mu , k - mu )$,
and $GAM sub inf ( fs D )$ is distance-regular with intersection array
$"{"v-1,2(k- lam -1),1;~1,2(k- lam -1),v-1"}"$ on $2v$ vertices.
.Ib 3 "%v-1,2(k- lam -1),1;~1,2(k- lam -1),v-1%"
Conversely, if $DEL$ is regular of valency $k$ such that
$fs D ( DEL )$ is regular, then $DEL$ is strongly regular
with parameters $(v,k, lam , mu )$, where
$lam = k - (v-a)/2$, $mu = k - a/2$ for $a = lam ( fs D )$,
and $k$ satisfies the quadratic equation
$2 k sup 2 - (v+2a) k + (v-1)a = 0$.
.Bop
$fs D ( DEL )$ is regular when $lam + (v - 2k + lam ) = 2(k - mu )$.
The parameters of $fs D sub inf$ and $GAM sub inf ( fs D )$
follow immediately.
Conversely, let $fs D = fs D ( DEL )$ be regular.
The $( minplus 1)$-matrices $S$ of all graphs in the switching class
of $fs D$ have the same spectrum - they satisfy
$S sup 2 = (v-2a-2) S + (v-1) I$.
For a regular graph $DEL$ we have $S = J - I - 2A$, so $A$ has
two eigenvalues distinct from $k$ and hence $DEL$ is strongly regular.
The parameters $lam$ and $mu$ follow by counting coherent triples:
$a = lam + mu bar = 2(k - mu )$.
The quadratic for $k$ follows by multiplying the above equation for $S$
by $J$.
.Eop
ADDITION.
On p. 16, at the end of Section 1.5, add references to
.SC Cameron
.[[
Cameron cohomological aspects 1977 Math
.]]
and
.SC Seidel
.[[
Seidel more about two-graphs 1990 Prachatice
.]].
ADDITION.
On p. 20, in Theorem 1.8.1, add a reference to
.SC Mulder
.[[
Mulder 1979 cubes graphs
.]].
ADDITION.
On p. 26, before the heading `The extended bipartite double
of a graph' insert the following fragment of text.
.LP
Generalizing the concept of bipartite double one may define the
\fIconjunction\fP
$GAM and DEL$ of two graphs $GAM , DEL$
as the graph with vertices $( gam , del )$ for $gam mo GAM$
and $del mo DEL$, and $( gam , del ) adj ( gam prime , del prime )$
if and only if $gam adj gam prime$ and $del adj del prime$.
It is easy to see (cf.
.SC Cvetkovi\*'c & Lu\*Vci\*'c
.[[
Cvetkovi\*'c generalization concept 1970
.]]
and
.SC Schwenk
.[[
Schwenk 1974 computing characteristic polynomial
.]])
that if $GAM$ has spectrum $PHI$ and $DEL$ has spectrum $PSI$,
then $GAM and DEL$ has spectrum $PHI . PSI$.
The bipartite double of $GAM$ is the special case where $DEL = K sub 2$.
ADDITION.
On p. 28, at the end of \(sc1.13, add:
.LP
.B Remark.
.SC Mulder
.[[
Mulder 1982 interval-regular
.]]
calls a graph \fIinterval\fP-\fIregular\fP
when it satisfies $c sub i = i$ for all $i$.
(Examples are $d$-cubes and folded $(2d+1)$-cubes; some
irregular examples are given in
.SC Mulder
.[[
Mulder 1982 interval-regular
.]]
and in
.SC Bandelt & Mulder
.[[
Bandelt Mulder 1984 interval-regular
.]],
where the case $d = 2$ is studied.)
He shows that these graphs are precisely the graphs
with the property that for any two vertices $gam , del$
the graph $I( gam , del )$ with as vertices and edges
the vertices and edges occurring in geodesics between
$gam$ and $del$ is a $d( gam , del )$-cube.
CORRECTION.
On p. 29, lines 3-4, change the sentence `Any ... entirely'
into `If $M$ is a maximal clique, and $gam , del mo M$, then
$M$ contains the singular line $"{" gam , del "}" sup { perp perp }$'.
On line 7, delete the word `in'.
ADDITION.
On p. 29, add after Lemma 1.14.1:
.LP
For arbitrary graphs one has:
.LP
.B
1.14.2 Lemma.
.I
In a graph $GAM$ any two singular lines have at most one point
in common if and only if $e sub 1 sup perp ib e sub 2 sup perp$
implies $e sub 1 sup perp = e sub 2 sup perp$ for any two
(intersecting) edges $e sub 1$ and $e sub 2$.
.Bop
Clearly, $beta mo "{" gam , del "}" sup { perp perp }$
is equivalent to $"{" gam , del "}" sup perp ib "{" beta , gam "}" sup perp$.
Hence $"{" beta , gam "}" sup { perp perp } =
"{" gam , del "}" sup { perp perp }$ if and only if
$"{" beta , gam "}" sup perp = "{" gam , del "}" sup perp$.
.Eop
CORRECTION.
On p. 29, Lemma 1.15.1, replace `Then' by `If $s >= 1$ and $t >= 0$, then'.
CORRECTION.
On p. 32, line 7 of the fourth proof, replace `$Rad b bar $'
by `$Rad q bar $'. Three lines later, add `and $q bar (x+y+z) = 0$'
after `$x+y+z mo R$'.
ADDITION.
On p. 33, change in the last line of the first remark `Brouwer
(both unpublished; ' into
.SC `Brouwer
.[[
Brouwer finite quadrangle 1991
.]]
('. Add at the end of this remark: `The advantage
of the fourth proof is that it generalizes to a classification
of all polar spaces with lines of size three'.
CORRECTION.
On p. 34 the proof of Proposition 1.16.1 was formulated
somewhat inaccurately. An amended version of the proof follows.
.LP
\&...
For any set $E ib GAM ( alpha ) ca GAM ( beta )$ define
$E sub alpha := "{" xi mo GAM ( alpha ) ca GAM sub 2 ( beta ) vb
"{" alpha , beta , xi "}" sup perp = E "}"$ and
$E sub beta := "{" xi mo GAM ( beta ) ca GAM sub 2 ( alpha ) vb
"{" alpha , beta , xi "}" sup perp = E "}"$.
Then, for $omega = alpha$ and $omega = beta$, we have
.EQ C
k sub GAM ( omega ) = mu + b sub 2 ( alpha , beta ) +
sum from E vb E sub omega vb ,~~~
k sub DEL ( omega ) = mu ( DEL ) + sum from { E cn gam }
vb E sub omega vb .
.EN
Since $k sub GAM ( alpha ) = k sub GAM ( beta )$ but
$k sub DEL ( alpha ) != k sub DEL ( beta )$, there must be a
proper subset $E$ of $GAM ( alpha ) ca GAM ( beta )$ such that
$vb E sub alpha vb != vb E sub beta vb$.
Now, if $xi mo E sub alpha$, ...
ADDITION.
On p. 36, in Remark (iii), add a reference to
.SC Ivanov & Shpectorov
.[[
Ivanov Shpectorov 1989 sporadic Petersen
.]].
CORRECTION.
On p. 37, Theorem 1.16.5 (iii), replace `\(sc12.1' by `\(sc12.2'.
ADDITION.
On p. 38, line 6, add after [639]: `and
.SC Gardiner
.[[
Gardiner antipodal coverings 1990
.]]
and Section 7.3 of
.SC Buckley & Harary
.[[
Buckley Harary distance 1990
.]]'.
HISTORICAL ADDITION.
On p. 40, in the attribution of 1.17.2, add `; J.A. Bondy, cf.
.SC Biggs
.[[
Biggs diameter three 1982
.]]'.
ADDITION.
On p. 40, Remarks, add:
.LP
(iii)
.SC Gardiner
.[[
Gardiner 1990 antipodal
.]]
further investigates distance regular graphs $DEL$
with intersection array $"{"k, k-1- lam ,1;~1,1,k"}"$
and finds the following (in the above notation):
.br
a) $c >= l-1$ with equality only for $c = 2$, i.e., for the
line graph of the Petersen graph.
[Indeed, if $C$ is a complete subgraph of $DEL sub 2 ( del )$,
then each point of $C$ has a neighbour on a different singular
line on $del$, so that $vb C vb <= c$. Choosing
$C = L ca DEL sub 2 ( del )$ for a singular line $L$ containing
an antipode of $del$ shows $c >= l-1$. If $c > 2$ we can find a
singular line contained in $DEL sub 2 ( del )$, so that $c >= l$.]
.br
b) If $c = l$, then $c = l = 2$ and $DEL$ is a hexagon.
[This follows from the standard feasibility conditions.]
.br
c) If $l = 4$, then $a = 41$. (No such graph is known.)
CORRECTION.
On p.\40, Theorem 1.17.4, change `b), c) or d)' into `b), c), d) or e)'.
In the proof, change `and the remark after the examples we have
b), c) or d)' into `we have e)'.
[Indeed, as A. Munemasa points out, the graph with $(v,a,l) = (21,4,3)$
obtained from a non-unitary polarity of $PG(2,4)$ is an example
of e), but not of b), c) or d).]
CORRECTION.
The proof of Proposition 1.17.7 given in
.SC Blokhuis & Brouwer
.[[
Blokhuis Brouwer geodetic 1988
.]]
contains a mistake (as was pointed out by D. Fon-der-Flaass).
Add on p. 42 in the first sentence of Proposition 1.17.7 a
third possibility:
.IP
.I
, or $B$ has precisely two components: one a line and the other
a distance-regular graph $DEL$ with intersection array
$"{"c-1,c-l,l;~1,1,c-l"}"$ on $c sup 2$ vertices
(so that $vb A vb = c l$ and $vb B vb = l + c sup 2$),
where $c = b - l + 1$.
.LP
In this additional case the graph $DEL sub 3$ is the block graph
of a transversal design $TD[l,c]$. There are two surviving
parameter sets on fewer than 49000 points, belonging to
$(l,c,v) = (5,21,551)$, $(4,40,1764)$. No examples are known.