ADDITION.
On p. 168, bottom, the question in Problem (ii) was (almost) answered
affirmatively by Hiroshi Suzuki.
.LP
.B
5.1.4. Proposition
.R
.SC (Suzuki
.[[
Suzuki distance-regular graphs 1990 equalki
.]]).
.I
If $GAM$ is distance-regular with $k sub i = k sub j$ where
$i < j$ and $i + j <= d$,
then either $GAM$ is antipodal (with $k sub d = 1$),
or $k sub l = k sub i$ for $i <= l <= j$.
Moreover, if in the latter case we have $k sub j != k sub j+1$,
then $p sub ij sup d = 0$ for $i + j > d+1$, so that in particular
$GAM sub d ( gam )$ is a clique for all $gam$.
.R
.Eop
.LP
.SC Hiraki, Suzuki & Wajima
.[[
Hiraki Suzuki Wajima
.]]
show that if $j+2 <= d$ then $k sub 2 = k sub j$ implies $k = 2$
or $k sub d = 1$.
ADDITION.
On p. 170 add after Remark (v) and before Corollary 5.2.2:
.LP
(vi) The inequalities (1) imply (by induction) that
.EQ C (*)
a sub j + 2 c sub j >= j ( lam + 2 ) ,
.EN
and, as the proof shows, one only needs local assumptions
(distance-regularity up to distance $j$) to prove this.
It would be interesting to characterize the graphs with
equality in (*); note that the geometric information in 5.2.1
is available for all $i <= j$. For $j = d$, (*) is equivalent
to Corollary 5.2.2 (and the equality case is characterized
in Theorem 5.2.3).
ADDITION.
On p. 171, add after Theorem 5.2.5:
.LP
In the case where $GAM$ has girth $2s$, Terwilliger's argument
can be sharpened to provide the diameter bound (3c) without
the restriction on $a sub s-1$ (Neumaier [pers. comm.]).
ADDITION.
On p. 172, strengthen Theorem 5.3.2 as follows:
.LP
.B
5.3.2. Theorem
.R
.SC (Godsil
.[[
Godsil bounding diameter
.]]).
.I
There are only finitely many coconnected distance-regular graphs
with an eigenvalue of fixed multiplicity $f > 2$.
Any such graph has diameter $d <= 3f - 4$ and valency
$k <= 1o2 (f - 1)(f + 2)$.
If $lam > 0$, then $d <= 2f - 2$.
If $lam = 0$, then $k <= f$.
.Bop
Let $f > 2$. If $d >= 3f - 3$ (or $d >= 2f - 1$ and $lam > 0$),
then the lemma implies
$b sub f-1 > 1$, and Proposition $DrgRep$.8 (iii) gives a
contradiction. Hence $d <= 3f - 4$, and the same proposition
gives $k = b sub 0 <= 1o2 (f - 1)(f + 2)$ (and $k <= f$ if $lam = 0$). ...
.Eop
ADDITION.
On p. 172, add:
.LP
.SC Suzuki
.[[
Suzuki distance-regular graphs 1993 biequalsone
.]]
improves the diameter bound of 5.3.2 to `$2d <= 5f-11$ when $GAM$ is not an
antipodal 2-cover' as a consequence of the following improvement to 5.3.1:
.I
If $GAM$ is distance-regular, not an antipodal 2-cover and not a polygon,
then if $b sub e = 1$ and $d >= 2e+1$, it follows that $2d <= 5e-8$.
.R
ADDITION.
On p. 172, add at the end of Remark (ii):
.LP
.SC Zhu
.[[
Zhu 1989
.]]
determined the distance-regular graphs with a multiplicity $f = 4$.
He finds $K sub 5$, $L(K sub 5 )$, $K sub 3,3$, $L(K sub 3,3 )$,
$T(5) bar$, $L( T(5) bar )$, the Pappus graph, the Desargues graph,
the 4-cube, the dodecahedron, $K sub { 4 times 2 }$, ${2 times 5} bar$
and $K sub { 5 times m }$ for $m >= 2$.
ADDITION.
The question in the problem on p. 174 was answered affirmatively by
.SC Lambeck
.[[
Lambeck thesis 1990
.]].
[Indeed, in the proof of 4.3.2 (iv)
we saw that if $b sub i > 1$ then there are singular lines of size
$lam + 2$, and any singular line meeting $GAM sub i ( gam )$ in at least
two points is contained in $GAM sub i ( gam ) cu GAM sub i+1 ( gam )$.
Viewed from a neighbour $gam sub 1$ of $gam$ we have a contradiction.]
CORRECTION.
In part (ii) of Proposition 5.5.1 (page 174) a restriction was omitted.
A corrected version follows.
.LP
.B
5.5.1. Proposition.
.I
Let $GAM$ be a distance-regular graph of diameter $d$ and
assume $lambda > 0$. Then, for
$i mo "{"1, ... , d-1"}"$:
.IP (i)
.I
$2 a sub i >= lam + 1$,
.IP (ii)
.I
$a sub i + a sub i+1 >= lam + 1$,
provided that $i < d-1$ or $a sub d > 0$ or ($d > 2$ and $b sub d-1 > 1$),
.IP (iii)
.I
$b sub i + c sub i+1 >= lam + 2$.
.Bop
Let $gam , del$ be two points of $GAM$ at distance $i+1$, and let
$gam = gam sub 0 , gam sub 1 , ... , gam sub i , gam sub i+1 = del$
be a geodesic from $ gam$ to $del$.
.br
(i) ...
.br
(ii)
By Lemma 4.1.7, the size
of $GAM sub i+1 ( gam ) ca GAM sub 2 ( gam sub i )$
is $p sub 2,i+1 sup i = b sub i ( a sub i + a sub i+1 - lam ) slash mu$
so that $a sub i + a sub i+1 >= lam$.
Suppose that $a sub i + a sub i+1 = lam$. Then by (i) we have $i = d-1$.
Since $p sub 2,d sup d-1 = 0$, each vertex of
$GAM ( del ) ca GAM sub d-1 ( gam )$ is adjacent to each vertex of
$GAM ( del ) ca GAM sub d ( gam )$.
If $a sub d > 0$, this means that ${ GAM ( del ) } bar$
is disconnected. But this contradicts Lemma $Regul$.1.7.
Hence $a sub d = 0$. If $b sub d-1 > 1$, then let
$del , del prime mo GAM ( gam sub d-1 ) ca GAM sub d ( gam )$.
We find $a sub 2 ( del , del prime ) = 0$, so by (i) we have $d = 2$.
.br
(iii) ...
.Eop
For a strengthening of part (ii), see inequality (4)
following Lemma $Param$.5.5.
The proviso in part (ii) is necessary, as shown by the antipodal graphs.
We do not know of nonantipodal cases where $a sub d-1 = lam$, $a sub d = 0$.
CORRECTION.
On p. 176, in Proposition 5.5.4 parts (i) and (ii), the condition
for equality is stated incorrectly. The text should read:
.LP
.B
5.5.4 Proposition
.R
.SC (Brouwer & Lambeck
.[[
Brouwer Lambeck inequality
.]]).
.I
Suppose the intersection array of a distance-regular graph
satisfies $a sub i != 0$, and define $a sub d+1 = 0$.
.IP (i)
.I
If $i < d$, then $b sub i <= a sub i + {a sub i+1 b sub i} over {a sub i}$,
and equality implies
$a sub i-1 >= a sub i >= a sub i+1$.
.IP (ii)
.I
If $i > 1$, then $c sub i <= a sub i + {a sub i-1 c sub i} over { a sub i}$,
and, for $i < d$, equality implies
$a sub i+1 >= a sub i >= a sub i-1$.
.IP (iii)
.I
If $ 1 <= i <= d$, then
$b sub i + c sub i <= a sub i + {a sub i+1 b sub i} over {a sub i} +
{a sub i-1 c sub i} over {a sub i}$, and
equality holds if and only if
for any four vertices $alpha$, $beta$, $gam$, $del$ of $GAM$
such that $alpha adj beta$, $gam adj del$, and $d( alpha , gam ) = i$,
the three distances $d( alpha , del )$, $d( beta , gam )$, $d( beta , del )$
are not all equal.
In particular, equality implies $a sub i+1 <= a sub i$ and
$a sub i-1 <= a sub i$.
.Bop
\&...
Similarly, we find $a sub i+1 <= a sub i$ in case
of equality in (i), and comparing with (iii) yields
$a sub i-1 >= a sub i$. For (ii) the proof is similar.
.Eop
CORRECTION.
On p. 178, delete lines $-8$, $-7$ and
the second inequality in 5.5.6 (i).
In the second and sixth line of the proof of 5.5.6, replace `$beta sup perp$'
by `$GAM ( beta )$'.
ADDITION.
On p. 179, add a Remark (iv):
.LP
.SC Nomura
.[[
Nomura inequalities distance-regular 1993
.]]
observes that if $c sub s = c sub s+t$ and $d( gam , del ) = t$, then
$GAM sub s ( gam ) ca GAM sub s+t ( del )$ is a subgraph of $GAM$
on $p sub s,s+t sup t$ vertices, regular of valency $a sub s$.
Thus, if $v(k,g)$ denotes the minimum number of vertices of
a graph of valency $k$ and girth $g$ (cf. \(sc6.9), and $GAM$
has girth $g$, then $p sub s,s+t sup t >= v(a sub s , g)$.
Similarly, if $b sub s = b sub s+t$, then
$p sub s,s+t sup t >= v(a sub s+t , g)$, and
if $b sub s = c sub t$, then $p sub s,t sup s+t >= v(a sub t , g)$.
Now $v(k,g)$ may be estimated by (21b) in \(sc6.7,
and we find restrictions for graphs with very large $a sub i$:
.LP
.B Lemma.
.I
Let $GAM$ have girth $g = 2r+1$.
.IP (i)
.I
If $2 a sub r >= k$ and $d >= 2r$, then $c sub 2r > 1$.
.IP (ii)
.I
If $c sub r+1 = 1$, then $(a sub r - 1) sup r < (k - 1) sup r-1 b sub r$.
.IP (iii)
.I
If $a sub e = ... = a sub e+m = k - 2 > 1$, then $m <= r-1$ and
$m < ( 1o2 + eps ) e$, where
$eps < 1/2(k-3) log (k-3)$. $eop$
.LP
ADDITION.
On p. 179, at the end of Section 5.5, add:
.Na "A" "4-vertex conditions"
Let $GAM$ be a distance-regular graph.
Given a finite metric space $fs X = (X,d)$, let $[ fs X ]$ be the
number of distance-preserving embeddings of $fs X$ into $GAM$.
In particular, when $vb X vb = 4$, we call the $[ fs X ]$
4-\fIvertex counts\fP; these satisfy
.EQ
define romantxt @ roman "$1" @
.EN
.KS
.IS
main {
var o,x,y,z;
o = (0,0);
x = cis(90);
y = cis(210);
z = cis(330);
conn o to x;
conn o to y;
conn o to z;
conn x to y;
conn x to z;
conn y to z;
right "\fIi \fP" at (x+y)/2;
left "\fI j\fP" at (z+x)/2 + (0,0.02);
"\fIr\fP" at (z+y)/2 - (0,0.23);
right "\fIl\fP" at x/2 - (0.05,0.13);
"\fIs\fP" at y/2 + (0.08, -0.1);
"\fIt\fP" at z/2 + (-0.12, -0.1);
"$sum from l ~ [$" at (-2,0);
"$] = v k sub r p sub st sup r p sub ij sup r ~ romantxt(for all) ~ i,j,r,s,t$" at (4,0);
"" at (-4,0);
"" at (8,0);
}
.IE
.KE
and, as a consequence of Theorem 2.3.2 (5),
.KS
.IS
main {
var o,x,y,z;
o = (0,0);
x = cis(90);
y = cis(210);
z = cis(330);
conn o to x;
conn o to y;
conn o to z;
conn x to y;
conn x to z;
conn y to z;
right "\fIi \fP" at (x+y)/2;
left "\fI j\fP" at (z+x)/2 + (0,0.02);
"\fIr\fP" at (z+y)/2 - (0,0.23);
right "\fIl\fP" at x/2 - (0.05,0.13);
"\fIs\fP" at y/2 + (0.08, -0.1);
"\fIt\fP" at z/2 + (-0.12, -0.1);
"$sum from i,j,l Q sub ia Q sub jb Q sub lc [$" at (-2,0);
"$] = 0 ~ romantxt(for all) ~ r,s,t ~ romantxt(and all) ~ a,b,c ~ romantxt(with) ~ q sub ab sup c = 0.$" at (5,0);
"" at (-4,0);
"" at (8,0);
}
.IE
.KE
These linear equations must be consistent with the nonnegativity constraints
$[ fs X ] >= 0$; for particular intersection arrays this can be checked by
standard linear programming software.
In particular, for $Q$-polynomial graphs,
.SC Terwilliger
.[[
Terwilliger counting vertex 1985
.]]
shows that all 4-vertex counts can be expressed as linear combinations
of the 4-vertex counts in which all distances are equal and at most
$[d/2]$. For $d = 3$ this allows us to express all 4-vertex counts
as linear functions of the number of 4-cliques,
and the nonnegativity constraints give lower and upper bounds
for this number. If one does this for the special case of
the intersection array $"{"19,12,5;1,4,15"}"$ (with $v = 96$)
one finds a contradiction, so that no such graph exists
.SC (Neumaier
.[[
Neumaier lecture 1989 configuration algebra
.]]).
CORRECTION.
On p. 181, Proposition 5.6.3, we wrote in a moment of unbelievable
blindness `if and only if', while three counterexamples to that
statement are given on the same page. This causes changes in three
places:
.br
On p.\145, line $-3$, delete the sentence `The graphs ... 5.6.3.'.
.br
On p. 180, line $-2$, delete `precisely the'.
.br
On p. 181, delete the `Conversely' part of the proof of Proposition 5.6.3,
and replace its statement by:
.LP
.B
5.6.3. Proposition.
.I
Let $GAM$ be distance-regular of diameter $d >= 3$, but not antipodal. If
$k = k sub d ( k sub d - 1)$ then $k sub d = a sub d + 1$,
i.e., $GAM sub d$ is a generalized Odd graph.
.R
ADDITION.
On p. 181, after the example following Lemma 5.6.4, add: `(Such graphs
are also ruled out by observing that $p sub 22 sup 1 = smover(7,2)$
is not integral.)'.
ADDITION.
On p. 181, at the end of Section 5.6, insert:
.SC `Suzuki
.[[
Suzuki bounding diameter part1 1991
.]]
shows that if $GAM sub d ( gam )$ is not a union of cliques,
and $c sub r = 1$, $a sub r = lam$, then $r < 2(k sub d - 1)$.
Using Ivanov's bound it follows that $d$ is bounded by a function
of $k sub d$ for distance-regular graphs $GAM$ for which
$GAM sub d ( gam )$ is not a union of cliques.
.SC Suzuki
.[[
Suzuki bounding diameter part2
.]]
extends this result and shows that $d$ is bounded by a function
of $k sub d$ for distance-regular graphs with $a sub d != 0$ and $k > 2$.
Let $h = max "{" i vb p sub di sup d != 0 "}"$ be the \fIheight\fP of $GAM$.
.SC Tomiyama
.[[
Tomiyama height 1996
.]]
studies graphs of height 2.'
ADDITION.
On p. 182, insert before the remark:
.LP
.B
5.7.2. Proposition
.R
.SC (Hiraki & Suzuki
.[[
Hiraki Suzuki distance regular graphs 1992
.]]).
.I
Let $GAM$ be a distance-regular graph with diameter $d$ and valency $k$.
Suppose that for some $e >= 1$ we have
$b sub i = c sub d-i$ for $1 <= i <= e$.
Then $c sub i = b sub d-i$ for $1 <= i <= e$, and if
$a := a sub d != 0$ then
$k = a(a+1)$, $b sub i = a sup 2$ for $1 <= i <= e$
and $c sub i = 1$ for $1 <= i <= e+1$.
.Eop
.LP
This implies another affirmative answer to Problem (iii)
on this page, earlier answered by Lambeck (see above, on p. 174).
ADDITION.
On p. 182, line $-5$, add to Problem (i), parenthetical remark:
.SC `Lambeck
.[[
Lambeck thesis 1990
.]]
shows that $d = 4$ is impossible, and gives some restrictions
in case $d = 3$'.
ADDITION.
On p. 182, Problem (iii) is equivalent to the problem on p. 174,
and was solved affirmatively by E.W. Lambeck (see above).
CORRECTION.
On p. 182, Problem (iv), the first occurrence of `$b sub i$'
should have been `$b sub d-1$'.
ADDITION.
On p. 183, strengthen Proposition 5.8.1 by adding that in case of
equality we have $vb "{" alpha , beta , gamma "}" sup perp vb =
mu (k - 2 - 2 lam ) / p$ for every triple $alpha , beta , gamma$
of vertices at pairwise distance 2.
CORRECTION.
On p. 185, third line to the right of the diagram should end
in $(i+2) sup {b sub i+1}$.
ADDITION.
On p. 189 the text in small print shows $v > d sup 2$ for $d >= 20$.
Using the same ideas one can derive a bound that is slightly better
and valid for all $d$.
.LP
.B
Proposition.
.I
Let $GAM$ be a distance-regular graph of diameter $d >= 4$ and valency
$k > 2$. Put $e = [(d-1)/3]$. Then
.EQ
v - 2 >= max ( 4 e sup 2 + (3k-2) e ,~~ 13 e sup 2 + e ).
.EN
.Bop
For $1 <= i < 1o3 d$ we have
$k sub i+1 = b sub i k sub i slash c sub i+1 > k sub i$,
so that $b sub i > c sub i+1$ and
.EQ C
k sub i+1 >= \(lc k sub i ( 1 + 1 over { c sub i+1 } ) \(rc >=
max ( k sub i + 2 , k sub i ( 1 + 1 over k-2 ) )
.EN
for these $i$. Now $k sub i slash c sub i+1 >= k sub i-1 slash c sub i$
(since $c sub i k sub i = b sub i-1 k sub i-1 >= c sub i+1 k sub i-1$
for $d >= 2i$), so
$k sub i >= k sub j + (i-j) e sub j$ for $1 <= j <= i$,
where $e sub j = \(lc k sub j slash c sub j+1 \(rc$.
Now Corollary $Param$.1.3 yields
.EQ I
v mark >= 2 sum from l=0 to j-1 k sub l + (i-j+1)(2k sub j + (i-j)e sub j ) +
(d-1-2i)(k sub j + (i-j+1)e sub j )
.EN
.EQ I (18)
lineup = 2 sum from l=0 to j-1 k sub l + (d+1-2j) k sub j +
(i-j+1)(d-1-i-j) e sub j .
.EN
In particular, with $j = 1$, $i = e$, this yields
.EQ C (19)
v - 2 >= (d-1)k + e(d-2-e) \(lc k slash mu \(rc
>= 3ek + 2e(2e-1) = 4e sup 2 + (3k-2)e . ~~~
.EN
This proves one of the two inequalities claimed, and the other
follows when $k >= 3e+1$, so we may assume $k <= 3e < d$, so that
$GAM$ is a Terwilliger graph.
If $k slash mu > 6$ then (19) yields the desired inequality, and
if $k <= 6 mu$, $mu > 1$ we are done by Corollary $Regul$.16.6 (ii).
If $k = 3$, all possible $GAM$ are known (see Theorem $DistTra$.5.1)
and our inequality follows by inspection of the list.
So, we may assume that $mu = 1$, $k mo "{"4,5,6"}"$ and (hence) $e >= 2$.
Applying (18) with $j = 2$, $i = e$ yields
.EQ I
v - 2 >= 2k + (3e-2)k sub 2 + 2(e-1) sup 2 \(lc k sub 2 slash c sub 3 \(rc .
.EN
But $c sub 3 < b sub 2 <= b sub 1$, so
$k sub 2 slash c sub 3 >= k b sub 1 slash (b sub 1 - 1)$
and we find the desired result unless $k = 4$, $b sub 1 = b sub 2 = 3$,
$c sub 3 = 2$, $k sub 2 = 12$, $k sub 3 = 18$, $e >= 11$.
This final case is settled either by estimating
$k sub i+1 >= k sub i (1 + 1 over k-2 ) >= 8 ( 3 over 2 ) sup i$
for $1 <= i <= e$, or by observing that (17) with $j = 2$
does not hold, so that we find a bound $d <= [2 cdot 14/3]+3 = 12$
on the diameter, contradicting $e >= 11$.
.Eop
CORRECTION.
On p. 190, line $-6$, replace `$u$' by `$zeta$'.
ADDITION.
On p. 191, replace lines 2-3 by `He conjectures that in fact $j > r$ is impossible
(which would yield a diameter bound $d <= k g$), cf.
.SC Ivanov
.[[
Ivanov problem algebraic metric deza frankl rosenberg 1988
.]]'.
ADDITION.
On p. 192, line $-5$ add:
.LP
.SC Hiraki
.[[
Hiraki improvement Boshier-Nomura bound
.]]
improved the above result to: if $r > 0$ then $s <= 3$.
ADDITION.
On p. 192 add at the end of the section:
.LP
.SC Higashitani & Suzuki
.[[
Higashitani Suzuki bounding 1992
.]]
show (using analytical methods) that the number of $i$ for
which $(c sub i , a sub i , b sub i ) = (1,k-2,1)$ is at most
$46 sqrt { k-3}$ when $k >= 5$.
.SC Hiraki
.[[
Hiraki circuit chasing triangles
.]]
shows (using circuit chasing) that if $lam > 0$ and
$(c sub i , a sub i , b sub i ) = (1, lam , b sub 1 )$ for $1 <= i < r$,
and $(c sub i , a sub i , b sub i ) = (2, 2 lam , b sub r )$
for $r <= i < r+j$, then $j <= 1$ (generalizing Gardiner's result
from $r = 2$ to arbitrary $r$).
.LP
.SC Suzuki
.[[
Suzuki distance-biregular divisible four
.]]
shows (using circuit chasing) that if
$(c sub 2j+1 , a sub 2j+1 , b sub 2j+1 ) = (1,0,k-1)$
and $(c sub 2j+2 , a sub 2j+2 , b sub 2j+2 ) = (2,0,k-2)$,
then $c sub 2j+3 > 2$.