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$.