# Non-geometric distance-regular graphs of diameter at least $3$ with smallest
eigenvalue at least $-3$

Jack H. Koolen 1, 2 Kefan Yu 1 Xiaoye Liang 3, 4
Harrison Choi 5 Greg Markowsky 5
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
1School of Mathematical Sciences, University of Science and Technology of
China, Hefei, China
2Wen-Tsun Wu Key Laboratory of the CAS, Hefei, China
3School of Mathematics and Physics, Anhui Jianzhu University, Hefei 230601, PR
China
4Operations Research and Data Science Laboratory, Anhui Jianzhu University,
Hefei 230601, PR China 5Department of Mathematics, Monash University,
Australia

###### Abstract

In this paper, we classify non-geometric distance-regular graphs of diameter
at least $3$ with smallest eigenvalue at least $-3$. This is progress towards
what is hoped to be an eventual complete classification of distance-regular
graphs with smallest eigenvalue at least $-3$, analogous to existing
classification results available in the case that the smallest eigenvalue is
at least $-2$.

##  1 Introduction

A great deal of information is known about regular graphs with smallest
eigenvalue at least $-2$. For instance, it was proved in [11] that if a
regular graph $\Gamma$ with more than $28$ vertices is connected and has
smallest eigenvalue at least $-2$, then it is either a line graph or a
cocktail party graph (see also [7, Theorem 3.12.2]). Furthermore, the strongly
regular graphs with smallest eigenvalue (at least) $-2$ have been completely
classified, and form a short list ([7, Theorem 3.12.4]). It is natural to
attempt to extend these results and to similarly understand regular graphs
with smallest eigenvalue at least $-3$. As one would expect, this is much
harder than the $-2$ case, but in recent years a number of researchers have
made significant contributions to this project. The purpose of this paper is
to expand knowledge in this area, and in particular to understand better non-
geometric distance-regular graphs with smallest eigenvalue at least $-3$.

The geometric distance-regular graphs with $c_{2}\geq 2$ and smallest
eigenvalue $-3$ have been completely classified in [1], [4], and [16].
Classifying all geometric distance-regular graphs with $c_{2}=1$ is still an
open problem, and it is probably very hard. Our focus then is on the non-
geometric case.

We will consider when the diameter is at least $3$ and the smallest eigenvalue
is at least $-3$ in this paper. Our main result is the following theorem.

######  Theorem 1.1.

Let $\Gamma$ be a non-geometric distance-regular graph with diameter at least
3. If the smallest eigenvalue of $\Gamma$ is at least $-3$, then one of the
following cases holds:

  1. (a)

$\Gamma$ is the Odd graph $O_{4}$ with $\iota(\Gamma)=\\{4,3,3;1,1,2\\}$;

  2. (b)

$\Gamma$ is the Sylvester graph with $\iota(\Gamma)=\\{5,4,2;1,1,4\\}$;

  3. (c)

$\Gamma$ is the second subconstituent of Hoffman-Singleton graph with
$\iota(\Gamma)=\\{6,5,1;1,1,6\\}$;

  4. (d)

$\Gamma$ is the Perkel graph with $\iota(\Gamma)=\\{6,5,2;1,1,3\\}$;

  5. (e)

$\Gamma$ is the symplectic $7$-cover of $K_{9}$ with
$\iota(\Gamma)=\\{8,6,1;1,1,8\\}$;

  6. (f)

the Coxeter graph $\iota(\Gamma)=\\{3,2,2,1;1,1,1,2\\}$;

  7. (g)

the dodecahedron with $\iota(\Gamma)=\\{3,2,1,1,1;1,1,1,2,3\\}$;

  8. (h)

the Biggs-Smith graph with $\iota(\Gamma)=\\{3,2,2,2,1,1,1;1,1,1,1,1,1,3\\}$;

  9. (i)

the Wells graph with $\iota(\Gamma)=\\{5,4,1,1;1,1,4,5\\}$;

  10. (j)

$\Gamma$ is the icosahedron with $\iota(\Gamma)=\\{5,2,1;1,2,5\\}$;

  11. (k)

$\Gamma$ is the Doro graph with $\iota(\Gamma)=\\{10,6,4;1,2,5\\}$;

  12. (l)

$\Gamma$ is the halved $6$-cube with $\iota(\Gamma)=\\{15,6,1;1,6,15\\}$;

  13. (m)

$\Gamma$ is the Gosset graph with $\iota(\Gamma)=\\{27,10,1;1,10,27\\}$;

  14. (n)

$\Gamma$ is the halved $7$-cube with $\iota(\Gamma)=\\{21,10,3;1,6,15\\}$;

  15. (o)

$\Gamma$ is the Klein graph with $\iota(\Gamma)=\\{7,4,1;1,2,7\\}$;

  16. (p)

$\Gamma$ is a distance-regular graph with $\iota(\Gamma)=\\{9,6,1;1,2,9\\}$;

  17. (q)

$\Gamma$ is a distance-regular graph with
$\iota(\Gamma)=\\{15,10,1;1,2,15\\}$;

  18. (r)

$\Gamma$ is a putative distance-regular graph with
$\iota(\Gamma)=\\{18,12,1;1,2,18\\}$.

Remark: When $\iota(\Gamma)=\\{9,6,1;1,2,9\\}$, by [30] we know that there
exist exactly two non-geometric examples (up to isomorphism). When
$\iota(\Gamma)=\\{15,10,1;1,2,15\\}$, there also exist non-geometric examples
by [9]. Section 9.1 below contains a detailed discussion of these two (and
other) cases.

Remark: The case $D=2$, the strongly regular case, requires (as usual) very
different techniques and is not addressed in this paper. The situation is
discussed in the recent paper [24], and the interested reader is referred
there.

This paper is devoted to the proof and discussion for this result. The
situation is fairly well understood when $\theta_{\min}\geq-2$, so we will
generally assume $-3\leq\theta_{\min}<-2$. All distance-regular graphs are
known when $a_{1}$ is large in relation to $k$, in particular when $k\leq
2a_{1}+2$ (see [26]). If $k\leq 2a_{1}+2$, then we have a Taylor graph, a line
graph, the Johnson graph $J(7,3)$ or the halved 7-cube. A line graph has
smallest eigenvalue at least $-2$ and the Johnson graph $J(7,3)$ is geometric.
So if $k\leq 2a_{1}+2$ we only have to consider the Taylor graphs and the
halved 7-cube.

The rest of the paper is organized as follows. In Sections 2 and 3, we will
give some definitions and preliminary results. In Section 4, we consider the
case when $c_{2}=1$; as is often the case in this field, this requires
different tools than the case $c_{2}>1$. In Section 5 we give the
classification when $\Gamma$ is a Taylor graph. In Section 6 we give the
classification when $\Gamma$ is a Terwilliger graph. In Section 7 we determine
a diameter bound and give an upper bound for $c_{2}$ when $\Gamma$ is non-
geometric and $-3\leq\theta_{\min}<-2,c_{2}\geq 2,k\geq 2a_{1}+3$. In Section
8, in order to search by computer, we use the bound in Section 7 to give an
upper bound on $a_{1}$. In Section 9 we present the resulting computational
results. In Section 10 we give the proof of the main theorem.

##  2 Combinatorial preliminaries

All the graphs considered in this paper are finite, undirected and simple (for
unexplained terminology and more details, see for example [7] or [31]). Let
$\Gamma$ be a connected graph and let $V(\Gamma)$ be the vertex set of
$\Gamma$. The distance $d(x,y)$ between any two vertices $x,y$ of $\Gamma$ is
the length of a shortest path between $x$ and $y$ in $\Gamma$. The diameter of
$\Gamma$ is the maximal distance occurring in $\Gamma$ and we will denote this
by $D=D(\Gamma)$. For a vertex $x\in V(\Gamma)$, define $\Gamma_{i}(x)$ to be
the set of vertices which are at distance $i$ from $x~{}(0\leq i\leq D)$, and
when the choice of $x$ is unimportant we will simply write $\Gamma_{i}$. In
addition, define $\Gamma_{-1}(x)=\Gamma_{D+1}(x)=\emptyset$. We write
$x\sim_{\Gamma}y$ or simply $x\sim y$ if two vertices $x$ and $y$ are adjacent
in $\Gamma$. A connected graph $\Gamma$ with diameter $D$ is called distance-
regular if there are integers $b_{i},c_{i}$ $(0\leq i\leq D)$ such that for
any two vertices $x,y\in V(\Gamma)$ with $d(x,y)=i$, there are precisely
$c_{i}$ neighbors of $y$ in $\Gamma_{i-1}(x)$ and $b_{i}$ neighbors of $y$ in
$\Gamma_{i+1}(x)$ (cf. [7, page 126]). In particular, a distance-regular graph
$\Gamma$ is regular with valency $k:=b_{0}$ and we define
$a_{i}:=k-b_{i}-c_{i}$ for notational convenience. The numbers $a_{i}$,
$b_{i}$ and $c_{i}~{}(0\leq i\leq D)$ are called the intersection numbers of
$\Gamma$, and the sequence
$\\{b_{0},b_{1},\ldots,b_{D-1};c_{1},c_{2},\ldots,c_{D}\\}$ is the
intersection array of $\Gamma$, we will denote it by $\iota(\Gamma)$. Note
that always $c_{0}=b_{D}=0$, $b_{0}=k$ and $c_{1}=1$.

There are two other related classes of graphs worth mentioning here. The first
are the strongly regular graphs, which are simply the distance-regular graphs
of diameter $2$. We say that a strongly regular graph $\Gamma$ has parameters
$(v,k,\lambda,\mu)$, where $v:=|V(\Gamma)|$, $\lambda:=a_{1}$, and
$\mu:=c_{2}$. The theory of these graphs is significantly different than that
of higher diameter distance-regular graphs, and for this reason they are often
identified separately.

The intersection numbers of a distance-regular graph $\Gamma$ with diameter
$D$ and valency $k$ satisfy (cf. [7, Proposition 4.1.6])

(i) $k=b_{0}>b_{1}\geq\cdots\geq b_{D-1}$;
(ii) $1=c_{1}\leq c_{2}\leq\cdots\leq c_{D}$;
(iii) $b_{i}\geq c_{j}$ if $i+j\leq D$.

Moreover, if we fix a vertex $x$ of $\Gamma$, then $k_{i}(x):=|\Gamma_{i}(x)|$
does not depend on the choice of $x$ as $c_{i}k_{i}(x)=b_{i-1}k_{i-1}(x)$
holds for $i=1,2,\cdots,D$, and thus $k_{i}:=k_{i}(x)=\frac{b_{0}b_{1}\cdots
b_{i-1}}{c_{1}c_{2}\cdots c_{i}}$. Define $k_{0}=1$ and $k:=k_{1}$. So
$v=|V(\Gamma)|=1+k+k_{2}+\cdots+k_{D}$.

By the _eigenvalues_ of a graph $\Gamma$, we mean the eigenvalues of its
adjacency matrix $A:=A(\Gamma)$. If the $\Gamma$ is distance-regular of
diameter $D$, its adjacency matrix $A$ has always exactly $D+1$ distinct
eigenvalues, and we will write $k=\theta_{0}>\theta_{1}>\cdots>\theta_{D}$ to
describe these distinct eigenvalues, and refer to
$\theta_{0},\ldots,\theta_{D}$ as simply the eigenvalues of $\Gamma$. Let
$m_{i}$ be the multiplicity of $\theta_{i}$ for $i=0,1,\ldots,D$, where
$m_{0}=1$, then we denote _spectrum_ of $\Gamma$ by the set
$\\{[\theta_{0}]^{m_{0}},[\theta_{1}]^{m_{1}},\cdots,[\theta_{D}]^{m_{D}}\\}$.
The matrix $A$ has all 0’s on the diagonal, and thus its trace is 0, which
implies that the sum of the eigenvalues (counting multiplicities) must be 0.
In particular, the eigenvalue of most importance for this paper, $\theta_{D}$,
is always negative.

We recall that the subgraph induced on a set of vertices $W\subseteq
V(\Gamma)$ is the subgraph with vertex set $W$ and edge set given by all edges
in $\Gamma$ connecting two vertices in $W$. The structure of the edges within
the subgraph induced on the set $\Gamma_{1}(x)$ is of special importance in
the theory of distance-regular graphs, and we will use the notation
$\Delta(x)$ to denote the subgraph induced on $\Gamma_{1}(x)$, and refer to
$\Delta(x)$ as the local graph at $x$.

A graph is called a clique if any two of its vertices are adjacent, and is
called coclique if any two of its vertices are nonadjacent. It is an
intriguing fact that the cliques of a strongly regular or distance-regular
graph have a close connection to the smallest eigenvalue of the graph, as we
now describe. If $\Gamma$ is a distance-regular graph with valency $k$ and the
smallest eigenvalue $\theta_{\min}$, then any clique $C$ of $\Gamma$ satisfies
the inequality

$|V(C)|\leq 1+\frac{k}{|\theta_{\min}|}.$ (2.0.1)

This is known as the Delsarte bound, as it was proved by Delsarte in [12] for
strongly regular graphs, later to be generalized by Godsil in [17] to
distance-regular graphs; see [7, Proposition 4.4.6] for two short proofs of
this. Equality may hold in (2.0.1), and any clique for which it does is called
a Delsarte clique. It is clear that if $\Gamma$ contains a Delsarte clique
then $\theta_{\min}$ must be an integer which divides $k$, since
$1+\frac{k}{|\theta_{\min}|}$ must be an integer ($\theta_{\min}$ is the root
of a polynomial with integer coefficients, so it can not be a non-integer
rational number).

An important concept for us will be that of a geometric distance-regular
graph; this is a distance-regular graph which contains a set of Delsarte
cliques ${\cal C}$ such that every edge of $\Gamma$ lies in a unique member of
${\cal C}$. This was first defined by Bose [6] in relation to strongly regular
graphs, later to be extended to distance-regular graphs by Godsil [17]. Many
of the most well-known families of distance-regular graphs are in fact
geometric, including the Johnson and Hamming graphs.

If $\Gamma$ is a distance-regular graph, then for any $i\in\\{1,\ldots,D\\}$
its distance $i$-graph is the graph with the same vertex set as $\Gamma$, with
two vertices adjacent if their distance is $i$ in $\Gamma$. $\Gamma$ is
bipartite if its distance 2-graph is disconnected, and antipodal if its
distance $D$-graph is disconnected. $\Gamma$ is primitive if its distance
$i$-graph is connected for all $i$, and imprimitive otherwise. A remarkable
theorem proved by Smith (see [7, Theorem 4.2.1]) shows that any imprimitive
distance-regular graph with valency $k\geq 3$ is either bipartite or antipodal
(or both).

An important fact about distance-regular graphs, and one we will take full
advantage of, is that, loosely speaking, all small distance-regular graphs are
known. To be precise,

  * •

All distance-regular graphs with $k=3$ are known (see [5] or [7, Theorem
7.5.1]).

  * •

All distance-regular graphs with $k=4$ are known (see [8]), except that there
is one graph on the list (generalized hexagon of order 3) which is not yet
known to be uniquely determined by its intersection array.

  * •

All feasible parameter sets for strongly regular graphs with at most 512
vertices are known (see [10, Chapter 12]).

  * •

All feasible parameter sets for primitive distance-regular graphs with
diameter 3 and at most 1024 vertices are known (see [7, Chapter 14]).

  * •

All feasible parameter sets for non-bipartite distance-regular graphs with
diameter 4 and at most 4096 vertices are known (see [7, Chapter 14]).

  * •

All feasible parameter sets for arbitrary distance-regular graphs with
diameter 5 or more and at most 4096 vertices are known (see [7, Chapter 14]).

The last three items here are of particular interest to us, for the following
reason. In many cases, we will be able to get a diameter bound on the graph in
question, and from this a bound on the number of vertices. When this number is
less than the relevant number above, we will often simply consult the tables
in order to determine whether any graphs satisfy our requirements. Note also
that bipartite graphs are not relevant to our results here, since a regular
bipartite graph of valency $k$ always has $-k$ as its smallest eigenvalue; if
$k\geq 4$ then this brings it below our cutoff of $-3$, and the $k=3$ case is
all classified anyway. Therefore, if a graph has diameter at least $4$ and at
most 4096 vertices, we know its intersection array must be found in the tables
in [7]. The same holds when the diameter $D=3$ and at most $1024$ vertices,
except that we will also have to worry about the antipodal (and not bipartite)
case.

##  3 Linear algebraic preliminaries

Linear algebraic methods are prominent in the study of distance-regular
graphs, and we will make heavy use of them. In this section, we collect some
facts that we will need.

Eigenvalue interlacing will be important for us, in particular the following
theorem, which is a simplification of the main theorem in [19] (only including
the parts of it that we will use).

######  Theorem 3.1 (cf. [19] ).

Let $A$ be a real symmetric $n\times n$ matrix with eigenvalues
$\theta_{1}\geq\cdots\geq\theta_{n}$. For some $m\leq n$, let $S$ be an
$n\times m$ real matrix such that $S^{\top}S$ is the $m\times m$ identity
matrix, and let $B=S^{\top}AS$ with eigenvalues
$\lambda_{1}\geq\cdots\geq\lambda_{m}$. Then the eigenvalues of B interlace
those of A, that is, $\theta_{i}\geq\lambda_{i}\geq\theta_{i+n-m}$, $1\leq
i\leq m$.

An equitable partition of a graph $\Gamma$ is a partitioning $\pi$ of the
vertex set of $\Gamma$ into classes $\\{P_{1},P_{2},...,P_{m}\\}$ such that
for every pair of (not necessarily distinct) indices
$i,j\in\\{1,2,\ldots,m\\}$ there is a nonnegative integer $s_{i,j}$ such that
each vertex $v\in P_{i}$ has exactly $s_{i,j}$ neighbors in $P_{j}$,
independent of the choice of $v$. We call the matrix $B=(s_{i,j})_{1\leq
i,j\leq m}$ the _quotient matrix_ of $\pi$. The following corollary shows that
the eigenvalues of $B$ interlace the eigenvalues of $\Gamma$.

######  Corollary 3.2 (cf.[19]).

Let $\Gamma$ be a graph on $n$ vertices with eigenvalues
$\theta_{1}\geq\cdots\geq\theta_{n}$, and suppose that $\pi$ is an equitable
partition with quotient matrix $B=(s_{i,j})_{1\leq i,j\leq m}$. Let the
eigenvalues of $B$ be $\lambda_{1}\geq\cdots\geq\lambda_{m}$. Then, for any
$i$ with $1\leq i\leq m$, we have
$\theta_{i}\geq\lambda_{i}\geq\theta_{i+n-m}$.

The interlacing results lead to a number of useful facts pertaining to
distance-regular graphs.

######  Lemma 3.3.

For a distance-regular graph $\Gamma$ with diameter $D\geq 4$, we have
$\theta_{1}\geq a_{1}+1$.

###### Proof.

Let $x$ be a vertex of $\Gamma$, and $H$ be the subgraph induced on
$\\{x\\}\cup\Gamma_{1}(x)$, then the equitable partition of $H$ formed by the
two sets $\\{x\\}$ and $\Gamma_{1}(x)$ leads to the quotient matrix

$\begin{pmatrix}0&k\\\ 1&a_{1}\end{pmatrix}.$ (3.0.1)

The largest eigenvalue of this matrix is
$\frac{1}{2}(a_{1}+\sqrt{a_{1}^{2}+4k})$, and thus the largest eigenvalue of
$H$ is at least this large by Corollary 3.2. Let now $x,y$ be two vertices
with $d(x,y)=4$, and let $H^{\prime}$ be the subgraph induced on
$\\{x\\}\cup\Gamma_{1}(x)\cup\Gamma_{1}(y)\cup\\{y\\}$. Then $H^{\prime}$ has
two connected components, and each has largest eigenvalue at least
$\frac{1}{2}(a_{1}+\sqrt{a_{1}^{2}+4k})\geq a_{1}+1$ by the previous argument.
By Corollary 3.2 again, $\Gamma$ has two eigenvalues at least the size of
$a_{1}+1$, in particular $\theta_{1}\geq a_{1}+1$. ∎

A tridiagonal matrix is a square matrix which is zero for all elements other
than those on the main diagonal and the diagonals immediately above and below
the main diagonal. Such matrices have many interesting properties, and these
will be valuable to us due the following proposition (see [7, pp. 128-130].

######  Lemma 3.4.

For a distance-regular graph $\Gamma$ of diameter $D$, consider the
tridiagonal $(D+1)\times(D+1)$-matrix

$L=\begin{pmatrix}0&k&&&&&\\\ 1&a_{1}&b_{1}&&&&\\\ &c_{2}&a_{2}&b_{2}&&&\\\
&&\ddots&\ddots&\ddots&&\\\ &&&&&b_{D-1}\\\ &&&&c_{D}&a_{D}\end{pmatrix}.$

Then the eigenvalues of $L$ are all distinct and agree with the distinct
eigenvalues of $\Gamma$. Further, consider the tridiagonal $D\times D$-matrix

$R:=\begin{pmatrix}-1&b_{1}&&&&\\\ 1&k-b_{1}-c_{2}&b_{2}&&&\\\
&c_{2}&k-b_{2}-c_{3}&&&\\\ &&\ddots&\ddots&\ddots&\\\ &&&&&b_{D-1}\\\
&&&&c_{D-1}&k-b_{D-1}-c_{D}\end{pmatrix}.$

Then the eigenvalues of $R$ are all distinct and agree with the distinct
eigenvalues of $\Gamma$ other than $k$.

We will derive some consequences from these useful facts, but first we must
take care of a technicality. Many powerful techniques, including eigenvalue
interlacing, can be applied to symmetric matrices, but the matrices $R$ and
$L$ are not symmetric. They can, however, be transformed in a simple manner
into symmetric matrices; this is explained in the following lemma, which is
certainly well known but is included for completeness. We omit the proof, as
it is direct calculation.

######  Lemma 3.5.

Let

$M:=\begin{pmatrix}z_{1}&y_{1}&&&&\\\ x_{2}&z_{2}&y_{2}&&&\\\
&x_{3}&z_{3}&\ddots&&\\\ &&\ddots&\ddots&&\\\ &&&&&y_{n-1}\\\
&&&&x_{n}&z_{n}\end{pmatrix}$

be a tridiagonal matrix with $y_{i}$, $x_{i+1}>0$ for $i=1,\ldots,n-1$, and
let

$N=diag(1,\sqrt{\frac{x_{2}}{y_{1}}},\sqrt{\frac{x_{2}x_{3}}{y_{1}y_{2}}},\ldots,\sqrt{\frac{x_{2}x_{3}\ldots
x_{n}}{y_{1}y_{2}\ldots y_{n-1}}}).$

Then the matrix $\tilde{M}=N^{-1}MN$ takes the form

$\tilde{M}:=\begin{pmatrix}z_{1}&\sqrt{x_{2}y_{1}}&&&&\\\
\sqrt{x_{2}y_{1}}&z_{2}&\sqrt{x_{3}y_{2}}&&&\\\
&\sqrt{x_{3}y_{2}}&z_{3}&\ddots&&\\\ &&\ddots&\ddots&&\\\
&&&&&\sqrt{x_{n}y_{n-1}}\\\ &&&&\sqrt{x_{n}y_{n-1}}&z_{n}\end{pmatrix}.$

In particular, $\tilde{M}$ is symmetric, and $M$ and $\tilde{M}$ share the
same spectrum.

The following lemma can be viewed as a version of eigenvalue interlacing, but
it will be easier to give a more direct proof since we require a strict
inequality.

######  Lemma 3.6.

Let $M=\\{m_{i,j}\\}_{i,j=1}^{n}$ be a symmetric, square, tridiagonal matrix
with smallest eigenvalue $\theta$. If we let
$M_{k}=\\{m_{i,j}\\}_{i,j=1}^{k}$, for some $k<n$, with smallest eigenvalue
$\theta_{k}$, and also have $m_{j+1,j}$ nonzero for $j=1,\ldots,n-1$, then
$\theta_{k}>\theta$.

###### Proof.

By the Courant minimax principle (see [22]), we have

$\theta_{k}=\min_{v\in{\mathbb{R}}^{k}\backslash\\{0\\}}\frac{v^{\top}M_{k}v}{v^{\top}v}.$

Choose $v_{k}$ which achieves this minimum, and form a vector
$\hat{v}\in{\mathbb{R}}^{n}$ by concatenating $v_{k}$ with a zero vector; that
is, the first $k$ entries of $\hat{v}$ agree with $v_{k}$, while the final
$n-k$ entries are zeros. Again by the minimax principle,

$\theta\leq\frac{\hat{v}^{\top}M\hat{v}}{\hat{v}^{\top}\hat{v}}=\frac{v_{k}^{\top}M_{k}v_{k}}{v_{k}^{\top}v_{k}}=\theta_{k}.$

We are after strict inequality, though, and to obtain that we may note that if
we had $\theta=\theta_{k}$ then $\hat{v}$ must be an eigenvector of $M$ with
eigenvalue $\theta$. However, if $j$ denotes the largest position of a nonzero
component of $\hat{v}$ (so $1\leq j\leq k<n$), then since $m_{j+1,j}$ is
nonzero the $(j+1)$-component of $M\hat{v}$ would be nonzero, and thus we
cannot have $M\hat{v}=\theta\hat{v}$. Thus, $\hat{v}$ is not an eigenvalue,
and the inequality is strict. ∎

The following lemma is immediate from Lemmas 3.4 through 3.6, and will find
use later.

######  Lemma 3.7.

With the reference to Lemma 3.4, let

$L_{j}=\begin{pmatrix}0&k&&&&&\\\ 1&a_{1}&b_{1}&&&&\\\
&c_{2}&a_{2}&b_{2}&&&\\\ &&\ddots&\ddots&\ddots&&\\\ &&&&&b_{j-1}\\\
&&&&c_{j}&a_{j}\end{pmatrix}$

for $j<D$. If the smallest eigenvalue of this matrix is $\theta_{j}$, and the
smallest eigenvalue of $\Gamma$ is $\theta_{D}$, then $\theta_{j}>\theta_{D}$.
The same coclusion holds for the matrix

$R_{j}:=\begin{pmatrix}-1&b_{1}&&&&\\\ 1&k-b_{1}-c_{2}&b_{2}&&&\\\
&c_{2}&k-b_{2}-c_{3}&\ddots&&\\\ &&\ddots&\ddots&&\\\ &&&&&b_{j}\\\
&&&&c_{j}&k-b_{j}-c_{j+1}\end{pmatrix}.$

We will now deduce some facts about distance-regular graphs from these lemmas.
In [23] it was shown that, if a distance-regular graph has smallest eigenvalue
at least $-m$, where $m$ is an integer and $m\geq 2$ , then $k<m(a_{1}+m)$. We
improve this result as follows.

######  Lemma 3.8.

Let $\Gamma$ be a distance-regular graph with intersection array
$\\{k,b_{1},\dots,b_{D-1};1,c_{2},\dots,c_{D}\\}$ and $D\geq 3$. For an
integer $m\geq 2$, if $\Gamma$ has smallest eigenvalue at least $-m$, then

$k<m(a_{1}+m)-(m-1)c_{2}.$

###### Proof.

Referring to the matrix $R$ of Lemma 3.4, consider the matrix $\tilde{M}$
which is the symmetrization (see Lemma 3.5) of $R+mI$. Note that the smallest
eigenvalue of $\tilde{M}$ is nonnegative. Following Lemma 3.6, if we form the
matrix

$\tilde{M}_{2}:=\begin{pmatrix}m-1&\sqrt{b_{1}}\\\
\sqrt{b_{1}}&m+k-b_{1}-c_{2}\end{pmatrix}$ (3.0.2)

then all eigenvalues of this matrix are strictly positive, and thus its
determinant is strictly positive. Rearranging (using $k-b_{1}=a_{1}+1$) yields
the lemma.

∎

We remark that, since our main concern is when $m$ is $3$, this result takes
the form $k<3a_{1}+9-2c_{2}$. The following lemma will also be useful.

######  Lemma 3.9.

Let $\Gamma$ be a distance-regular graph with intersection array
$\\{k,b_{1},\dots,b_{D-1};1,c_{2},\dots,c_{D}\\}$ and distinct eigenvalues
$k=\theta_{0}>\theta_{1}>\cdots>\theta_{D}$. Then we have

$\theta_{1}\geq\max\\{-1,k-b_{1}-c_{2},k-b_{2}-c_{3},\ldots,k-b_{D-1}-c_{D}\\}.$

###### Proof.

We first symmetrize the matrix $R$ as in Lemma 3.5, obtaining a symmetric
matrix $\tilde{R}$ with the same diagonal elements. We will then apply Theorem
3.1 with the matrix $S$ being an $(D\times 1)$-vector with a $1$ in the $r$-th
spot and zero everywhere else. The resulting matrix $B=S^{\top}RS$ is simply a
$(1\times 1)$-matrix whose lone entry is the $r$-th element along the diagonal
of $\tilde{R}$, and thus of $R$. Theorem 3.1 tells us that $\theta_{1}$ is at
least as large as the eigenvalue of $B$, which is simply the $r$-th diagonal
element of $R$. Applying this for each $r$ yields the result. ∎

##  4 The distance-regular graphs with $c_{2}=1$

As indicated in the introduction, the geometric distance-regular graph with
smallest eigenvalue $\theta_{\min}=-3$, $c_{2}\geq 2$ and diameter at least 3
have been classified. This was begun by Bang [1], who started the
classification of geometric distance-regular graphs with smallest eigenvalue
$-3$ and $c_{2}\geq 2$, and the results of Bang and Koolen [4] and Gavrilyuk
and Makhnev [16] completed the classification.

In this section we focus on the $c_{2}=1$ case. We concentrate on a non-
geometric distance-regular graph $\Gamma$ with smallest eigenvalue
$\theta_{\min}$ where $-3\leq\theta_{\min}<-2$, $c_{2}=1$, and diameter at
least 3. Before stating any new results, we describe the situation more
carefully.

Since $c_{2}=1$, the local graph $\Delta$ is a disjoint union of
$(a_{1}+1)$-cliques, and the largest cliques in $\Gamma$ are therefore of size
$a_{1}+2$. Furthermore, each edge is contained in a unique such
$(a_{1}+2)$-clique. As $a_{1}+1$ divides $k$, the quantity
$t=\frac{k}{a_{1}+1}$ is an integer, and if we had $\theta_{\min}=-t$ then
$\Gamma$ would be geometric. Since we are excluding this case, we obtain
information from this observation, as we now describe.

Let $\cal{C}$ denote the set of $(a_{1}+2)$-cliques in $\Gamma$. Let $M$
denote the vertex-clique matrix; this is the
$|V(\Gamma)|\times|\mathcal{C}|$-matrix with $M_{i,j}=1$ if vertex $i$ is in
clique $C_{j}$ and 0 otherwise. Each pair of adjacent vertices lies in a
unique clique in $\cal{C}$, and each vertex is in $t$ such cliques. We
therefore have $A=MM^{\top}-tI$. Since $\Gamma$ is not geometric it cannot
have $-t$ as an eigenvalue, and it follows from this that the
$|V(\Gamma)|\times|V(\Gamma)|$-matrix $MM^{\top}$ is of full rank (no zero
eigenvalue), and thus that the rank of $M$ is also $|V(\Gamma)|$. This can
only happen if $|\mathcal{C}|\geq|V(\Gamma)|$. We have
$(a_{1}+2)|\mathcal{C}|=t|V(\Gamma)|$, since both quantities represent the
number of 1’s in $M$, and therefore $a_{1}\leq t-2$. We isolate this as a
lemma.

######  Lemma 4.1.

Let $\Gamma$ be a non-geometric distance-regular graph with diameter $D\geq 3$
and $c_{2}=1$. Then $a_{1}\leq t-2$, where $t=\frac{k}{a_{1}+1}$.

The case $t=2$ (more generally, all distance-regular graphs with $k\leq
2a_{1}+2$ and $D\geq 3$) has also been classified, in [26, Theorem 16]. In all
cases with $t\leq 2$ we have $\theta_{\min}\geq-2$ (in fact, the case $t=2$
can only occur for line graphs by [7, Proposition 4.3.4]). We will therefore
assume $\theta_{\min}<-2$, which forces $t\geq 3$. The following lemma
characterises the possibilities which may occur.

######  Lemma 4.2.

Let $\Gamma$ be a distance-regular graph with smallest eigenvalue
$-3\leq\theta_{\min}<-2$, $D\geq 3$, and $c_{2}=1$. Then
$t=\frac{k}{a_{1}+1}\geq 3$, and the pair

$(k,a_{1})\in\\{(3,0),(4,0),(5,0),(6,0),(6,1),(8,1),(12,2)\\}.$

###### Proof.

Suppose first that $t=3$. By Lemma 4.1, $a_{1}\leq 1$. This then gives us two
possibilities, $(k,a_{1})\in\\{(3,0),(6,1)\\}$. Similarly, $t=4$ implies
$a_{1}\leq 2$ by Lemma 4.1, and we have the possibilities
$(k,a_{1})\in\\{(4,0),(8,1),(12,2)\\}$.

Now assume $t\geq 5$. Even though the bound on $a_{1}$ given by Lemma 4.1 is
growing weaker, we obtain a stronger bound now by Lemma 3.8, which shows
$k\leq 3a_{1}-2c_{2}+8=3a_{1}+6$. We must therefore have $3a_{1}+6\geq
ta_{1}+t$, and this can only occur with $t=5,6$ and $a_{1}=0$. This yields the
remaining two cases, $(k,a_{1})\in\\{(5,0),(6,0)\\}$. ∎

We will now examine each of the cases given in Lemma 4.2. Some of these cases
have already been classified in other papers, while others will require a more
detailed analysis. Recall that we are searching for non-geometric distance-
regular graphs with $c_{2}=1$, $D\geq 3$, and $\theta_{\min}\geq-3$. We first
assume $D=3$.

From Lemma 4.2, by checking the feasible intersection arrays in [7, Chapter
14], we obtain the following corollary.

######  Corollary 4.3.

Let $\Gamma$ be a non-geometric distance-regular graph with
$-3\leq\theta_{\min}<-2$, $c_{2}=1$ and diameter $3$. Then $\Gamma$ is one of
the following:

  1. (a)

the Odd graph $O_{4}$ with $\iota(\Gamma)=\\{4,3,3;1,1,2\\}$;

  2. (b)

the Sylvester graph with $\iota(\Gamma)=\\{5,4,2;1,1,4\\}$;

  3. (c)

the second subconstituent of the Hoffman-Singleton graph with
$\iota(\Gamma)=\\{6,5,1;1,1,6\\}$;

  4. (d)

the Perkel graph with $\iota(\Gamma)=\\{6,5,2;1,1,3\\}$;

  5. (e)

the symplectic $7$-cover of $K_{9}$ with $\iota(\Gamma)=\\{8,6,1;1,1,8\\}$.

###### Proof.

Since $b_{1}<k$, we have $k_{2}\leq k^{2}-k$ and $k_{3}<k^{3}-k^{2}$. So the
total number of vertices $v$ is less than $k^{3}+1$. When $k=3,4,5,6,8$, we
have $v<1024$. To obtain this same bound for $k=12$ is a bit more work, but
can obtain it by applying Lemma 3.7 to the matrix

$\begin{pmatrix}0&12&0\\\ 1&2&9\\\ 0&1&a_{2}\end{pmatrix}.$

To simplify matters in this and a number of future cases, we employed a
computer algebra software to handle such calculations; Mathematica notebooks
containing the relevant calculations are available with the arxiv version of
this paper.

The software tells us that this matrix has minimum eigenvalue less than or
equal to $-3$ whenever $a_{2}\leq 6$, and thus we can assume $a_{2}\geq 7$ and
$b_{2}\leq 4$. Now $v=1+k+k_{2}+k_{3}\leq 1+k+kb_{1}+k{b_{1}b_{2}}<1024$ (as
$c_{3}\geq c_{2}=1$). Therefore, in all cases, we can simply use the tables in
[7], together with the characterization of antipodal non-bipartite graphs of
diameter 3 given in the same section.

First, we look for primitive distance-regular graphs in the table of feasible
intersection arrays in [7, Chapter 14]. We find that $\Gamma$ can be the Odd
graph $O_{4}$, the Sylvester graph, the Perkel graph or the putative distance-
regular graph with $\iota(\Gamma)=\\{5,4,3;1,1,2\\}$. This last one has been
eliminated by Fon-Der-Flaass in [15].

Next we consider the imprimitive distance-regular graph, and as mentioned
before we only need to discuss the antipodal covers of distance-regular graphs
with intersection array $\\{k,b_{1},1;1,1,k\\}$. By Lemma 4.2, we know that
$(k,b_{1})\in\\{(3,2),(4,3),(5,4),(6,5),(6,4),(8,6),$ $(12,9)\\}$. We can
immediately dispense with $(k,b_{1})=(3,2)$ using the known classification of
cubic distance-regular graphs (see [5] or [7, Theorem 7.5.1]): there are none
with intersection array $\\{3,2,1;1,1,3\\}$. The case $(k,b_{1})=(6,4)$ can
also be handled with known classification results, since here $a_{1}=1$ and
thus any such graphs would have to be contained in the list in [21], and since
all graphs there are geometric, there are none meeting our requirements. For
the others, when $(k,b_{1})\neq(8,6)$, we find $a_{1}\neq c_{2}$, in this case
the eigenvalues are all integers. Then we have $\theta_{\min}=-3$. Since
$\theta_{\min}$ is the solution of the equation $x^{2}+(c_{2}-a_{1})x-k=0$, it
follows that $2k-3b_{1}+3=0$. So $(k,b_{1})$ only can be $(6,5)$ or $(12,9)$.
The first one is the second subconstituent of the Hoffman-Singleton graph with
$\iota(\Gamma)=\\{6,5,1;1,1,6\\}$, and the second one is eliminated because
the multiplicity of $-3$ is not integral by [7, page 431]. When
$(k,b_{1})=(8,6)$, we find $\Gamma$ is the Symplectic $7$-cover of $K_{9}$
with $\iota(\Gamma)=\\{8,6,1;1,1,8\\}$. This proves the corollary. ∎

Next, we discuss the $D\geq 4$ case.

######  Corollary 4.4.

Let $\Gamma$ be a non-geometric distance-regular graph with
$-3\leq\theta_{\min}<-2$, $c_{2}=1$ and diameter $D\geq 4$. Then $\Gamma$ is
one of the following:

  1. (a)

the Coxeter graph with $\iota(\Gamma)=\\{3,2,2,1;1,1,1,2\\}$;

  2. (b)

the dodecahedron with $\iota(\Gamma)=\\{3,2,1,1,1;1,1,1,2,3\\}$;

  3. (c)

the Biggs-Smith graph with $\iota(\Gamma)=\\{3,2,2,2,1,1,1;1,1,1,1,1,1,3\\}$;

  4. (d)

the Wells graph with $\iota(\Gamma)=\\{5,4,1,1;1,1,4,5\\}$.

###### Proof.

We will proceed case by case.

Case $(3,0)$: The cubic distance-regular graphs have been classified, in [5].
The ones which meet our conditions are the Coxeter graph, the dodecahedron,
and the Biggs-Smith graph.

Case $(4,0)$: The distance-regular graphs of valency 4 have been classified,
in [8]. None of them meet our conditions.

Case $(5,0)$: It is easy to see that if $D=4$ then the number of vertices is
less than 1000, and we can use the tables. So we need only consider $D$ large.
We had the computer algebra software calculate the smallest eigenvalue of the
matrix

$\begin{pmatrix}0&5&0&0&0\\\ 1&0&4&0&0\\\ 0&1&4-b_{2}&b_{2}&0\\\
0&0&c_{3}&5-c_{3}-b_{3}&b_{3}\\\ 0&0&0&c_{4}&a_{4}\end{pmatrix},$

where $b_{2}$ ranged from 1 to 4, $b_{3}$ ranged from 1 to $b_{2}$ (because
the $b_{i}$’s are decreasing), $c_{4}$ ranged from 1 to $b_{3}-1$, and $c_{3}$
ranged from 1 to $c_{4}$ (because the $c_{i}$’s are increasing). The
requirement $c_{4}\leq b_{3}-1$ is due to [7, Corollary 5.9.7], which states
that if $c_{i+1}\geq b_{i}$ then $D\leq 3i$; in our case, if $c_{4}\geq b_{3}$
then $D\leq 9$, which means that the number of vertices is less than
$1+5+20+80+6\times 80=586$. With these requirements, we found only the
following partial intersection arrays

$\begin{split}\\{5,4,3,3,\ldots;1,1,1,1,\ldots\\},\\\
\\{5,4,3,2,\ldots;1,1,1,1,\ldots\\},\\\
\\{5,4,2,2,\ldots;1,1,1,1,\ldots\\}.\end{split}$ (4.0.1)

However, all three of these parameter sets satisfy $a_{1}=0,b_{2}\neq b_{1}$,
and $c_{4}=1$. But [20, Corollary 4.7] asserts that no such distance-regular
graphs can exist. Thus the only possible graphs in this case can be found in
the tables.

Examining the tables gives only the Wells graph and a putative distance-
regular graph with $\iota(\Gamma)=\\{5,4,3,3;1,1,1,2\\}$, however this latter
graph has been shown not to exist in [14].

Case $(6,0)$: Similar to the previous case, we had the computer algebra system
calculate the smallest eigenvalue of the matrix

$\begin{pmatrix}0&6&0&0&0\\\ 1&0&5&0&0\\\ 0&1&5-b_{2}&b_{2}&0\\\
0&0&c_{3}&6-c_{3}-b_{3}&b_{3}\\\ 0&0&0&c_{4}&a_{4}\end{pmatrix}.$

where $b_{2}$ ranged from 1 to 5, $b_{3}$ ranged from 1 to $b_{2}$ (because
the $b$’s are decreasing), $c_{4}$ ranged from 1 to $b_{3}-1$, and $c_{3}$
ranged from 1 to $c_{4}$ (because the $c$’s are increasing). The requirement
$c_{4}\leq b_{3}-1$ is for the same reason as the previous case. With these
requirements, we found only the following partial intersection array

$\\{6,5,2,2,\ldots;1,1,1,1,\ldots\\}.$ (4.0.2)

As in the previous case, we have $a_{1}=0,b_{2}\neq b_{1}$, and $c_{4}=1$;
thus no distance-regular graph can have this intersection array. Thus, again,
the only possible graphs in this case can be found in the tables. However, no
graphs satisfying our requirements can be found there.

Case $(6,1)$: Fortunately for us, all distance-regular graphs with
$(k,a_{1})=(6,1)$ have been classified by Hiraki, Nomura and Suzuki [21], and
it turns out that all the graphs there are geometric. Therefore there are none
that meet our requirements.

Case $(8,1)$: We begin by applying Lemma 3.7 to the matrix

$\begin{pmatrix}0&8&0\\\ 1&1&6\\\ 0&1&a_{2}\end{pmatrix}.$

The computer algebra software told us that this matrix has minimum eigenvalue
less than or equal to $-3$ whenever $a_{2}\leq 1$, and thus we can assume
$a_{2}\geq 2$. We know then that $c_{3}\geq 2$ from [7, Theorem 4.3.11], and
thus $c_{4}\geq 2$ as well. We then had the computer algebra software
calculate the smallest eigenvalue of the matrix

$\begin{pmatrix}0&8&0&0&0\\\ 1&1&6&0&0\\\ 0&1&7-b_{2}&b_{2}&0\\\
0&0&c_{3}&8-c_{3}-b_{3}&b_{3}\\\ 0&0&0&c_{4}&a_{4}\end{pmatrix},$

where $b_{2}$ ranged from 1 to 5 (because $a_{2}\geq 2$), $b_{3}$ ranged from
1 to $b_{2}$ (because the $b_{i}$’s are decreasing), $c_{4}$ ranged from 2 to
$b_{3}-1$ (for the same reason as the previous two cases), and $c_{3}$ ranged
from 2 to $c_{4}$ (because the $c$’s are increasing). With these requirements,
we found only the following partial intersection array

$\\{8,6,3,3,\ldots;1,1,2,2,\ldots\\}.$ (4.0.3)

However, in this case, by Theorem 1.1 of [3], $c_{5}>c_{3}=2$, so $c_{4}\geq
b_{4}$. By [7, Corollary 5.9.7], the diameter $D\leq 12$, and thus the number
of vertices is bounded above by $1+8+48+72+108+8\times 108<4096$. Thus the
only possible graphs in this case can be found in the tables in [7]. However,
no graphs with $(k,a_{1})=(8,1)$ can be found there.

Case $(12,2)$: There does not exist a distance-regular graph with
$(k,a_{1},c_{2})=(12,2,1)$ and $\theta_{\min}\geq-3$, as we now show.

We know that $c_{3}\geq 2$ from [7, Theorem 4.3.11]. Furthermore, by Theorem
1.1 of [3] this implies that $c_{5}>c_{3}$, so $c_{5}\geq 3$, and the same
theorem implies that $c_{9}>c_{5}$, so $c_{9}\geq 4$.

Let us suppose that $b_{4}\leq 3$. Then, as $c_{9}>b_{4}$, we must have that
the diameter is at most 12 (see Proposition 2.4 of [31]). Using
$k_{i}=\frac{b_{0}b_{1}\cdots b_{i-1}}{c_{1}c_{2}\cdots c_{i}}$, we can bound
$k_{1}=12,k_{2}=108,k_{3}\leq 216,k_{4}\leq 432$, and then $k_{j}\leq 432$ for
$j=5,\ldots,8$ since $c_{5}\geq b_{4}$, the $c$’s are increasing, and the
$b$’s are decreasing. Furthermore, for $j=9,\ldots,D$ we have
$\frac{b_{j-1}}{c_{j}}\leq 3/4$, and thus $k_{9}\leq 324$, $k_{10}\leq 243$,
$k_{11}<183$, and $k_{12}<138$. Thus, the number of vertices of the graph is
at most $1+12+108+216+5\times 432+324+243+183+138<4096$, and we are done. So
we may assume $b_{2}=b_{3}=b_{4}=4$.

Suppose now that $b_{5}<c_{5}$. Then by Proposition 2.4 of [31] the diameter
of the graph is at most 9, and we can bound as before
$k_{1}=12,k_{2}=108,k_{3}\leq 216,k_{4}\leq 432,k_{5}\leq 576$, and then
$k_{5}>k_{j}$ for $j=6,7,8,9$ since $c_{j}>b_{j-1}$ for $j\geq 6$. We see that
the number of vertices of the graph is at most $1+12+108+216+432+5\times
576<4096$, and we are done. Thus we can assume $b_{5}\geq c_{5}$.

We now turn again to the computer algebra software. We will apply Lemma 3.7
once more, this time to the matrix

$\begin{pmatrix}0&12&0&0&0&0\\\ 1&2&9&0&0&0\\\ 0&1&7&4&0&0\\\
0&0&c_{3}&8-c_{3}&4&0\\\ 0&0&0&c_{4}&8-c_{4}&4\\\
0&0&0&0&c_{5}&a_{5}\end{pmatrix}.$

It is now a matter of calculating the smallest eigenvalue for each matrix of
this type, as $c_{3}$ varies from 2 to 4, $c_{4}$ varies from $c_{3}$ to 4,
$c_{5}$ varies from 3 to 4, and $a_{5}$ is equal either $8-c_{5}$ or $9-c_{5}$
(since $3\leq c_{5}\leq b_{5}\leq b_{4}=4$). The computer algebra system now
tells us that every single one of these matrices has smallest eigenvalue
strictly smaller than $-3$. Thus, again, the only possible graphs in this case
can be found in the tables. However, no graphs satisfying our requirements can
be found there. ∎

##  5 Taylor graphs

A distance-regular graph with intersection array $\\{k,c_{2},1;1,c_{2},k\\}$
is called _Taylor graph_. In this section we determine the Taylor graphs with
smallest eigenvalue at least $-3$.

######  Proposition 5.1.

Let $\Gamma$ be a non-geometric Taylor graph with smallest eigenvalue
$\theta_{\min}$. If $-3\leq\theta_{\min}<-2$, then $\Gamma$ is the
icosahedron, the halved 6-cube or the Gosset graph.

###### Proof.

Suppose $\Gamma$ has intersection array $\\{k,c_{2},1;1,c_{2},k\\}$ and
distinct eigenvalues $\theta_{0}=k>\theta_{1}>\theta_{2}>\theta_{3}$. The
eigenvalues $\theta_{1},\theta_{3}$ are roots of $x^{2}-(a_{1}-c_{2})x-k$. So,
if $\theta_{3}=-3$, then $k=3c_{2}-3a_{1}-9$. This implies that
$a_{1}=2c_{2}-4$, as $k=a_{1}+c_{2}+1.$ As the 3-cube and the Johnson graph
$J(6,3)$ are geometric, we find by [7, Corollary 1.15.3] that $\Gamma$ is the
Gosset graph or the halved 6-cube and both graphs are not geometric. Now we
assume that $-3\theta_{3}>-2$. Then $a_{1}=c_{2}$ and $\theta_{3}=-\sqrt{k}$.
Moreover, any local graph is a connected strongly regular graph with at most 8
vertices, having no non-trivial integer eigenvalues. this means that any local
graph must be the pentagon and $\Gamma$ the icosahedron.

This shows the proposition. ∎

##  6 Terwilliger graphs

A Terwilliger graph is a connected non-complete graph such that, for any two
vertices $u,v$ at distance two, the subgraph induced on
$\Gamma_{1}(u)\cap\Gamma_{1}(v)$ in $\Gamma$ is a clique of size $\mu$ (for
some fixed $\mu\geq 0$); clearly in the context of distance-regular graphs we
have $\mu=c_{2}$. Note also that a Terwilliger graph does not contain induced
quadrangles. In this section, we determine the Terwilliger graphs satisfying
$D\geq 3$. First, for $\theta_{D}$, we give a generalized result, then we
apply this result to our assumption.

######  Proposition 6.1.

Let $\Gamma$ be a distance-regular graph with diameter $D\geq 3$ and smallest
eigenvalue $\theta_{D}$. Assume that $\Gamma$ is a Terwilliger graph and
$c_{2}\geq 2$. If $\theta_{D}\geq-5$, then $\Gamma$ is one of the following:

  * (1)

The icosahedron with intersection array $\\{5,2,1;1,2,5\\}$ and
$\theta_{3}=-\sqrt{5}$;

  * (2)

The Doro graph with intersection array $\\{10,6,4;1,2,5\\}$ and
$\theta_{3}=-3$ (see [7, Proposition 12.2.2]);

  * (3)

The Conway-Smith graph with intersection array $\\{10,6,4,1;1,2,6,10\\}$ and
$\theta_{4}=-4$ (see [7, Section 13.2B]);

  * (4)

$\Gamma$ is locally the Hoffman-Singleton graph (and $c_{2}=2$).

###### Proof.

Assume $\theta_{D}\geq-5$ and $c_{2}\geq 2$. From Lemma 3.8, we have $k\leq
5a_{1}-4c_{2}+24\leq 5a_{1}+16$. If $k\leq(6+\frac{8}{57})(a_{1}+1)$, we are
done by [26, Proposition 6(3)]. So let $5a_{1}+16\geq
k>(6+\frac{8}{57})(a_{1}+1)$. This means $a_{1}\leq 8$ and hence $k\leq 56$.

When $k<50(c_{2}-1)$, we also done by [7, Corollary 1.16.6]. We now assume
$k\geq 50(c_{2}-1)\geq 50$. So $c_{2}=2$. This implies that, by [7, Theorem
1.16.3], any local graph of $\Gamma$ is a strongly regular graph with
parameters $(k,a_{1},\lambda,1)$ and $50\leq k\leq 56$, and hence is the
Hoffman-Singleton graph with parameters $(50,7,0,1)$ with distinct eigenvalues
$7,2,-3$ (in this case, $\theta_{D}<-3$ by [27, Corollary 3.7]). This shows
the result. ∎

If the smallest eigenvalue of $\Gamma$ is at least $-3$, we directly obtain
the following corollary.

######  Corollary 6.2.

Let $\Gamma$ be a Terwilliger graph with diameter $D\geq 3$ and $c_{2}\geq 2$.
If the smallest eigenvalue $\theta_{D}\geq-3$, then $\Gamma$ is the
icosahedron or the Doro graph.

##  7 The distance-regular graphs with diameter $D\geq 3$ and $k\geq
2a_{1}+3,~{}c_{2}\geq 2,~{}\theta_{D}\geq-3$

In this section, we discuss the distance-regular graphs $\Gamma$ with diameter
$D\geq 3$, valency $k\geq 2a_{1}+3$, intersection number $c_{2}\geq 2$ and
smallest eigenvalue $\theta_{D}\geq-3$. Note that by Lemma 3.8 we have
$-3\leq\theta_{D}<-2$ and $2a_{1}+3\leq k\leq 3a_{1}+4$, and thus $\Gamma$
must be non-geometric except for the case $k=3a_{1}+3$. The case when $\Gamma$
does not contain an induced quadrangle is handled in Section 6, and we will
therefore assume that $\Gamma$ contains an induced quadrangle. We will deduce
in this case a diameter bound and a bound on $c_{2}$. We will employ the
following two lemmas from [7].

######  Lemma 7.1 (cf. [7, Theorem 5.2.1, Corollary 5.2.2]).

Let $\Gamma$ be a distance-regular graph with diameter $D$. If $\Gamma$
contains an induced quadrangle, then

$\displaystyle c_{i}-b_{i}\geq c_{i-1}-b_{i-1}+a_{1}+2\quad(i=1,\cdots,D).$
(7.0.1)

Furthermore,

$D\leq\frac{k+c_{D}}{a_{1}+2},$

with equality if and only if equality holds in (7.0.1) for all i.

######  Lemma 7.2 (cf. [7, Theorem 5.2.3]).

Let $\Gamma$ be a distance-regular graph with diameter
$D\geq\frac{k+c_{D}}{a_{1}+2}$. Then one of the following holds:

  * (i)

$\Gamma$ is a Terwilliger graph,

  * (ii)

$\Gamma$ is strongly regular with smallest eigenvalue $-2$,

  * (iii)

$\Gamma$ is a Hamming graph, a Doob graph, a locally Petersen graph, a Johnson
graph, a halfcube, or the Gosset graph.

We remark that if $\Gamma$ in the above lemma has smallest eigenvalue
$-3\leq\theta_{D}<-2$ and is not a Terwilliger graph (see Section 6), then
$D\leq 4$; this observation will be useful in proving Proposition 7.7 later.

The following lemma determines the bounds for intersection numbers $b_{2}$ and
$c_{3}$.

######  Lemma 7.3.

Let $\Gamma$ be a distance-regular graph with diameter $D\geq 3$. Assume
$\Gamma$ contains an induced quadrangle and has smallest eigenvalue
$\theta_{D}\geq-3$. Then $b_{2}\leq\frac{1}{2}b_{1}+\frac{1}{2}$ and
$c_{3}\geq b_{3}+2c_{2}-2$.

###### Proof.

We have $k\leq 3a_{1}-2c_{2}+8$ by Lemma 3.8 and $c_{i}-b_{i}\geq
c_{i-1}-b_{i-1}+a_{1}+2$ for $i=1,2\dots,D$ by Lemma 7.1. It follows that
$b_{1}\leq 2a_{1}-2c_{2}+7$, and thus

$\displaystyle b_{2}$ $\displaystyle\leq b_{1}+c_{2}-a_{1}-3$
$\displaystyle\leq\frac{1}{2}b_{1}+\frac{2a_{1}-2c_{2}+7}{2}+c_{2}-a_{1}-3$
$\displaystyle=\frac{1}{2}b_{1}+\frac{1}{2},$

and

$\displaystyle c_{3}$ $\displaystyle\geq b_{3}+c_{2}-b_{2}+a_{1}+2$
$\displaystyle\geq b_{3}+c_{2}-\frac{1}{2}b_{1}-\frac{1}{2}+a_{1}+2$
$\displaystyle\geq b_{3}+2c_{2}-2.$

This proves the lemma. ∎

Whether or not $\Gamma$ contains an an induced $4$-claw (i.e. an induced
$K_{1,4}$) will now determine our approach. The following ”claw bound” will be
valuable.

######  Lemma 7.4 (cf.[25, Lemma 2, Proposition 3]).

Let $\Gamma$ be a distance-regular graph with valency $k$ and diameter $D\geq
2$. If $\Gamma$ contains an induced $K_{1,t}$, say $x,x_{1},\ldots,x_{t}$ for
$t\geq 2$, then

$c_{2}\geq\frac{t(a_{1}+1)-k}{\binom{t}{2}}-1.$

Furthermore, if equality holds and all induced paths of length $2$ lie in an
induced $K_{1,t}$ then $\Gamma$ is a Terwilliger graph.

From the above lemma and Lemma 3.8 we obtain the following result.

######  Lemma 7.5.

Let $\Gamma$ be a distance-regular graph with diameter $D\geq 3$, and let
$2\leq m<t$ be integers. If $\Gamma$ contains an induced $K_{1,t}$ and
$\theta_{D}\geq-m$, then

$c_{2}\geq\frac{(t-m)(a_{1}+1)-m(m-1)+\binom{t}{2}+1}{\binom{t}{2}-m+1}.$

###### Proof.

By Lemma 3.8 we have $k\leq m(a_{1}+m)-(m-1)c_{2}-1$. On the other hand, we
have $k\geq t(a_{1}+1)-{\binom{t}{2}}(c_{2}-1)$ by Lemma 7.4. This means

$\left(\binom{t}{2}-m+1\right)c_{2}\geq(t-m)(a_{1}+1)-m(m-1)+\binom{t}{2}+1.$

So $c_{2}\geq\frac{(t-m)(a_{1}+1)-m(m-1)+\binom{t}{2}+1}{\binom{t}{2}-m+1}$.
This proves the lemma. ∎

From Lemma 7.4, if $\Gamma$ contains an induced $K_{1,4}$ we immediately
obtain the following lower bound for $c_{2}$.

######  Corollary 7.6.

Let $\Gamma$ be a distance-regular graph with diameter $D\geq 3$. If $\Gamma$
contains an induced $K_{1,4}$ and $\theta_{D}\geq-3$, then
$c_{2}\geq\frac{a_{1}+2}{4}$.

Note that, in this case, by [1, Theorem 3.2], we know that $\Gamma$ is non-
geometric. The following proposition gives the diameter bound.

######  Proposition 7.7.

Let $\Gamma$ be a distance-regular graph with diameter $D\geq 3$,
$\theta_{D}\geq-3$ and $k\geq 2a_{1}+3$. If $\Gamma$ contains an induced
quadrangle, then $D\leq 4$.

###### Proof.

Note that $\Gamma$ contains an induced $K_{1,3}$ and $c_{2}\geq 2$. If
$\Gamma$ contains an induced $K_{1,3}$ but no induced $K_{1,4}$, then by [2,
Lemma 2.10 (3)] we are done. So we assume $\Gamma$ contains an induced
$K_{1,4}$. Then by Corollary 7.6, we have $c_{2}\geq\frac{a_{1}+2}{4}$. And by
Lemma 7.1 and 7.2 we have $c_{i}-b_{i}\geq c_{i-1}-b_{i-1}+a_{1}+2$ for
$i=1,2\dots,D$ and $D<(k+c_{D})/(a_{1}+2)$.

Assume that $D\geq 5$. Then $2k\geq(k+c_{D})>5(a_{1}+2)$. As
$c_{2}\geq\frac{a_{1}+2}{4}$ and $k\leq 3a_{1}-2c_{2}+8$, we may fix $k\leq
2\frac{1}{2}a_{1}+7$, and then
$k\in\\{2\frac{1}{2}a_{1}+5\frac{1}{2},2\frac{1}{2}a_{1}+6,2\frac{1}{2}a_{1}+6\frac{1}{2},2\frac{1}{2}a_{1}+7\\}$.
This implies $c_{2}\leq\frac{3a_{1}+8-k}{2}\leq\frac{a_{1}}{4}+\frac{5}{4}$.
Let $t>0$ be an integer. If $a_{1}\in\\{4t,4t+1,4t+2\\}$, then $c_{2}=t+1$ and
if also $a_{1}=4t+3$ then $c_{2}=t+2$.

Using $\frac{5}{2}a_{1}+5<k\leq 3a_{1}-2c_{2}+8$ and the fact that $k\cdot
a_{1}$ is an even integer (the handshake lemma applied to $\Gamma_{1}$) we
find the following possibilities for the quadruple $(k,a_{1},b_{1},c_{2})$:

$\displaystyle(k,a_{1},b_{1},c_{2})\in\\{$
$\displaystyle(10t+12,4t+2,6t+9,t+1),$ $\displaystyle(10t+11,4t+2,6t+8,t+1),$
$\displaystyle(10t+8,4t+1,6t+6,t+1),$ $\displaystyle(10t+6,4t,6t+5,t+1)\\}.$

Now, $k_{2}=\frac{k\cdot b_{1}}{c_{2}}$ must be an integer. This doesn’t help
us in the $k=10t+8$ case just described, since there $c_{2}\big{|}b_{1}$, but
in the other three cases it severely restricts the possible values of $t$. It
may be checked that the following are the only cases which may occur.

$\displaystyle t\in\\{5,2,1\\},$ $\displaystyle\text{ if }k=10t+12,$
$\displaystyle t\in\\{1\\},$ $\displaystyle\text{ if }k=10t+11,$
$\displaystyle t\in\\{3,1\\},$ $\displaystyle\text{ if }k=10t+6.$

Let $k=10t+12$ and $t=5$. Then $k=62,~{}k_{2}=k\cdot\frac{b_{1}}{c_{2}}=403$,
$D<\frac{2k}{a_{1}+2}=\frac{2\times 62}{24}<6$. So we obtain $D=5$. By Lemma
7.3, we have $b_{2}\leq\frac{1}{2}b_{1}+\frac{1}{2}=20$ and $c_{3}\geq
b_{3}+2c_{2}-2\geq 3c_{2}-2\geq 16$. As a result,

$\displaystyle k_{3}=k_{2}\cdot\frac{b_{2}}{c_{3}}\leq
403\times\frac{20}{16}\leq 503,$ $\displaystyle
k_{4}=k_{3}\cdot\frac{b_{3}}{c_{4}}\leq 503\times\frac{20}{16}\leq 628,$
$\displaystyle k_{5}=k_{4}\cdot\frac{b_{4}}{c_{5}}\leq
628\times\frac{20}{16}=785.$

So the order of $\Gamma$ is equal to $1+k+k_{2}+k_{3}+k_{4}+k_{5}\leq 2400$.
Consulting the tables in [7, Chapter 14], we find none that match these
requirements, and we are done in this case.

The other cases for $k=10t+12$ with $t=2,1$, $k=10t+6$ and $k=10t+11$ go in
same fashion, and we leave them to the reader. So we are left with the case
$k=10t+8$.

Let $k=10t+8$, so that $k_{2}=k\cdot\frac{b_{1}}{c_{2}}=6k$. We have
$b_{2}\leq\lfloor\frac{1}{2}b_{1}+\frac{1}{2}\rfloor=3t+3$ and $c_{3}\geq
3c_{2}-1=3t+2$ (as $b_{2}<\frac{1}{2}b_{1}+\frac{1}{2}$). It follows that
$c_{3}\in\\{3t+2,3t+3\\}$, and thus $k_{3}=k_{2}\cdot\frac{b_{2}}{c_{3}}\leq
6k\cdot\frac{3t+3}{3t+2}$. Note that $b_{3}\leq b_{2}-c_{2}+c_{3}-a_{1}-2\leq
3t+3-(t+1)+3t+3-4t-3=t+2$ and $c_{4}\geq b_{4}+c_{3}-b_{3}+a_{1}+2\geq
1+3t+2-(t+2)+4t+3\geq 6t+4$. Thus,

$k_{4}=k_{3}\cdot\frac{b_{3}}{c_{4}}\leq
6k\cdot\frac{3t+3}{3t+2}\cdot\frac{t+2}{6t+4},$
$k_{5}=k_{4}\cdot\frac{b_{4}}{c_{5}}\leq
6k\cdot\frac{3t+3}{3t+2}\cdot(\frac{t+2}{6t+4})^{2}.$

It follows that $k_{4}+k_{5}\leq 2k$ unless $t\leq 2$. If $t\leq 2$, we obtain
that $v\leq 2048$ and consulting the tables [7, Chapter 14] allows us to close
this case.

If $t\geq 3$, then [29, Theorem 2(2)] and [7, Theorem 5.1.2] imply that
$\Gamma$ is a diameter 5 antipodal 2-cover of a strongly regular graph (which
we denote $\Delta$). As $\theta_{D}\geq-3$, the graph $\Delta$ has smallest
eigenvalue more than $-3$. Thus, $\Delta$ is a conference graph or $\Delta$ is
a strongly regular graph with smallest eigenvalue $-2$. In the first case
$a_{1}=\frac{1}{2}k-1$ and we are done by [26, Theorem 16]. In the second case
we have $k\leq 28$ or $c_{2}\in\\{2,4\\}$ by [7, Theorem 3.12.4]. Since
$c_{2}=t+1$, this implies that $t\leq 3$ and thus $k=10t+8\leq 38$. Note that
$\Delta$ and $\Gamma$ have the same $a_{1}$ and $c_{2}$. As $\Gamma$ is an
antipodal $2$-cover of $\Delta$, we have $|V(\Gamma)|=2|V(\Delta)|$, so that
$v=2(1+k+k_{2})\leq 534$. We finish once again by consulting [7, Chapter 14].

This completes the proof. ∎

In [2, Proposition 2.11], it was shown that a distance-regular graph $\Gamma$
which has $k>\frac{8}{3}(a_{1}+1)$, $c_{2}\geq 2$, and no induced $K_{1,4}$
must be geometric with smallest eigenvalue $-3$. On the other hand, if
$\Gamma$ is a non-geometric distance-regular graph with smallest eigenvalue
$\theta_{D}\geq-3$, and if the valency $k\geq 2a_{1}+3$, then
$c_{2}\geq\frac{a_{1}-5}{6}$ by [31, Proposition 9.9]. We will improve this
lower bound on $c_{2}$ later.

The following results about geometric distance-regular graphs will be
required; they are due to Metsch (see [28] or [31, Proposition 9.1]).

######  Proposition 7.8.

Let $\Gamma$ be an distance-regular graph with valency $k$ and diameter $D\geq
2$. Assume that the following two properties hold for some positive integer
$m\geq 1$:

  1. (1)

$a_{1}\geq(2m-1)(c_{2}-1)$,

  2. (2)

$k<(m+1)(a_{1}+1)-\frac{1}{2}m(m+1)(c_{2}-1)$.

Define a line to be a maximal clique $C$ satisfying $|V(C)|\geq
a_{1}+2-(m-1)(c_{2}-1)$. Then every vertex is on at most $m$ lines and any
edge lies in a unique line.

The following proposition was shown by Van Dam, Koolen and Tanaka, see [31,
Proposition 9.8].

######  Proposition 7.9.

Let $\Gamma$ be a distance-regular graph with diameter $D$ with the property
that there exists a positive integer $m$ and a set $\mathcal{C}$ of cliques in
$\Gamma$ such that every edge is contained in exactly one clique of
$\mathcal{C}$ and every vertex $x$ is contained in exactly $m$ cliques of
$\mathcal{C}$. If $|{\mathcal{C}}|<|V(\Gamma)|$, then $\Gamma$ is geometric
with smallest eigenvalue $-m$. In particular, this is the case if
$\min\\{|V(C)|\mid C\in{\mathcal{C}}\\}>m$.

As a consequence of Propositions 7.8 and 7.9 we have:

######  Theorem 7.10.

Let $\Gamma$ be a distance-regular graph with smallest eigenvalue
$\theta_{\min}\geq-3$, $c_{2}\geq 2$ and $k\geq 2a_{1}+3$. If $a_{1}\geq
5(c_{2}-1)$ and $k<4(a_{1}+1)-6(c_{2}-1)$, then $\Gamma$ is geometric with
$\theta_{\min}=-3$.

###### Proof.

By Proposition 7.8, every vertex lies on at most $3$ lines and any edge lies
on a unique line, where a line is a maximal clique $C$ satisfying $|V(C)|\geq
a_{1}+2-2(c_{2}-1)$. Note that any line has at least $3(c_{2}-1)+2\geq 5$
vertices. As $k\geq 2a_{1}+3$, we see that every vertex lies on exactly $3$
lines as a line can not have more than $a_{1}+2$ vertices. Hence we are done
by Proposition 7.9. ∎

Combining the conclusions above, we obtain a the following useful corollary.

######  Corollary 7.11.

Let $\Gamma$ be a distance-regular graph that has an induced quadrangle but no
$K_{1,4}$’s. If $\theta_{\min}\geq-3$, $k\geq 2a_{1}+3$ and
$c_{2}<\frac{a_{1}+6}{5}$, then $\Gamma$ is geometric.

###### Proof.

It is easy to verify that $\Gamma$ has an induced $K_{1,3}$ and $c_{2}\geq 2$.
Assume that $\Gamma$ is not geometric. If $\Gamma$ has no induced $K_{1,4}$,
as mentioned earlier, we obtain that $k\leq\frac{8}{3}(a_{1}+1)$ by [2,
Proposition 2.11]. Then
$4(a_{1}+1)-6(c_{2}-1)\geq(4-\frac{6}{5})(a_{1}+1)+\frac{6}{5}>\frac{8}{3}(a_{1}+1)\geq
k$, however this contradicts Theorem 7.10. ∎

It is known by Corollary 7.6 that if a distance-regular graph $\Gamma$ has an
induced $K_{1,4}$, then $c_{2}\geq\frac{a_{1}+2}{4}$. In fact, this can be
improved in the case that $\Gamma$ is not geometric and has induced
quadrangles. The following proposition asserts that, under these assumptions,
the case $\frac{a_{1}+2}{4}\leq c_{2}<\frac{a_{1}+6}{5}$ does not occur.

######  Proposition 7.12.

Let $\Gamma$ be a distance-regular graph with $D\geq 3$, $\theta_{D}\geq-3$,
$c_{2}\geq 2$ and $k\geq 2a_{1}+3$. If $\Gamma$ is non-geometric and contains
an induced quadrangle, then $c_{2}\geq\frac{a_{1}+6}{5}$.

###### Proof.

Assume that $\Gamma$ is not geometric. If $c_{2}\leq\frac{1}{5}(a_{1}+1)$, we
have $4(a_{1}+1)-6(c_{2}-1)\leq k\leq 3a_{1}-2c_{2}+8$ by Theorem 7.10 and
Lemma 3.8, which implies that $c_{2}\geq\frac{a_{1}+2}{4}$. This shows that
$5\leq a_{1}\leq 10$. Because $c_{2}$ is an integer, we may assume
$\lceil\frac{a_{1}+2}{4}\rceil\leq c_{2}\leq\lfloor\frac{a_{1}+5}{5}\rfloor$,
and then the possibilities for the pair $(a_{1},c_{2})$ are
$(5,2),~{}(6,2),~{}(10,3)$.

Assume now that $\Gamma$ has an induced $K_{1,4}$ (otherwise we may simply
apply Corollary 7.11). For the case $(a_{1},c_{2})=(5,2)$, we have
$k=18=3(a_{1}+1)$, and then $\Gamma$ has no an induced $K_{1,4}$ by [2, Lemma
4.3], a contradiction. For the other cases, because $\Gamma$ contains an
induced quadrangle we obtain $D\leq 4$ by Proposition 7.7. If
$(a_{1},c_{2})=(6,2)$, then $k=22$, $k_{2}=k\cdot\frac{b_{1}}{c_{2}}=165$, and
$k_{3}=k_{2}\cdot\frac{b_{2}}{c_{3}}\leq
k_{2}\cdot\frac{\frac{1}{2}(b_{1}+1)}{(2c_{2}-2)}=660$ by Lemma 7.3. So $v\leq
1+k+k_{2}+k_{3}+k_{4}\leq 2(1+k+k_{2}+k_{3})<2048$. We may therefore check the
feasible array table in [7, Chapter 14], and we find that this parameter set
does not exist. The case $(a_{1},c_{2})=(10,3)$ can be shown to be non-
existent in the same way. ∎

##  8 Bound for $a_{1}$

In this section, we suppose that the distance-regular graph $\Gamma$ has the
same constraints as in Section 7. Suppose further that $\Gamma$ is non-
geometric and contains an induced quadrangle. In order to search for feasible
arrays for $\Gamma$ with the aid of a computer, we will find an upper bound
for $a_{1}$. We have already reduced to the case $2a_{1}+3\leq k\leq
3a_{1}-2c_{2}+8$. By Proposition 7.12, we have $c_{2}\geq\frac{a_{1}+6}{5}$
and then $k\leq\frac{13a_{1}+28}{5}$. We will assume $a_{1}\geq 44$, so that
$c_{2}\geq 10$ and $k\leq\frac{13a_{1}+28}{5}\leq\frac{8}{3}(a_{1}+1)$; since
we are looking for an upper bound on $a_{1}$, and this upper bound will be
greater than 44, this assumption on $a_{1}$ is no restriction. The following
lemma will be crucial for us.

######  Lemma 8.1.

Let $\Gamma$ be a distance-regular with $v$ vertices, valency $k$, diameter
$D\geq 3$ and distinct eigenvalue $k=\theta_{0}>\theta_{1}>\dots>\theta_{D}$
with respective multiplicities $m_{0}=1,m_{1},\dots,m_{D}$. Let
$\zeta=\frac{v-1}{k},~{}\gamma=\frac{\theta_{1}}{a_{1}+1},~{}\delta=\frac{k}{a_{1}+1}$.
Assume there exist an $N\leq 4$ such that
$\frac{k}{N}\leq\min\\{m_{1},m_{D}\\}$. Then
$a_{1}+1\leq\frac{N(\zeta-1)\delta}{\gamma^{2}}$.

###### Proof.

We have $vk=\sum_{i=0}^{D}m_{i}\theta_{i}^{2}\geq
k^{2}+m_{1}\theta_{1}^{2}+m_{D}\theta_{D}^{2}$. As $\Gamma$ is regular and
non-complete, we find $\theta_{D}\leq-2$. So we obtain

$\displaystyle(\zeta k+1)\cdot k$ $\displaystyle\geq
k^{2}+\frac{k}{N}\theta_{1}^{2}+\frac{k}{N}\theta_{D}^{2}$ $\displaystyle\geq
k^{2}+\frac{k}{N}\theta_{1}^{2}+\frac{k}{N}\cdot 4$

Therefore $\theta_{1}^{2}\leq N(\zeta-1)k$.

By the definition of $\gamma,\delta$ we find that
$a_{1}+1\leq\frac{N(\zeta-1)\delta}{\gamma^{2}}$. ∎

We will obtain an upper bound for $a_{1}$ according to the above Lemma in this
section. Let us start with discussing parameter $N$. Suppose the distance-
regular graph $\Gamma$ has distinct eigenvalues
$k=\theta_{0}>\theta_{1}>\cdots>\theta_{D}$ with respective multiplicities
$m_{0}=1,m_{1},\cdots,m_{D}$. By [27, Theorem 3.6] and [7, Theorem 4.4.3(ii),
4.4.11], we only need to discuss the cases that the second largest eigenvalue
$\theta_{1}$ satisfies $\frac{b_{1}}{2}-1<\theta_{1}<b_{1}-1$ (as
$\theta_{D}\geq-3$).

When $m_{1}\geq k$, we can assume $N\leq 1$, which satisfies the condition of
Lemma 8.1. When $m_{1}<k$, we have known from [7, Theorem 4.4.4] that if
$\theta_{1}\notin\mathbb{Z}$, $\theta_{1}$ and $\theta_{D}$ are conjugate
algebraic integers, hence $m_{1}=m_{D}$; if $\theta_{1}\in\mathbb{Z}$,
$\theta_{1}$ divides $b_{1}-1$ which is not in the scope of our discussion. So
we will discuss $N$ when $m_{1}<k$ and $\theta_{1}\notin\mathbb{Z}$.

In this case, it follows that $m_{D}=m_{1}<k$ and then the local graph of
$\Gamma$ has an eigenvalue $-\frac{b_{1}}{\theta_{D}+1}-1$ with multiplicity
at least $k-m_{D}$ by [7, Theorem 4.4.4]. Then we have

$\displaystyle ka_{1}\geq
a_{1}^{2}+(k-m_{D})(-\frac{b_{1}}{\theta_{D}+1}-1)^{2},$
$\displaystyle\implies~{}~{}$ $\displaystyle
a_{1}(b_{1}+1)\geq(k-m_{D})(\frac{b_{1}}{2}-1)^{2}.$

Since $k\geq 2a_{1}+3$, we have $a_{1}\leq b_{1}-2$. It follows that
$(b_{1}-2)(b_{1}+1)\geq\frac{1}{4}(k-m_{D})(b_{1}-2)^{2}$. One can easily
check that $m_{D}\geq k-4$, so $m_{1}\geq k-4\geq 0.956k$ as $k\geq
2a_{1}+3\geq 91$. Thus, we have $N\leq\frac{1}{0.956}$. Note that this upper
bound value is greater than 1, so we always assume $N\leq\frac{1}{0.956}$
whether $m_{1}\geq k$ or $m_{1}<k$.

The next two propositions utilize Lemma 8.1 to provide upper bounds for
$a_{1}$ when $\Gamma$ has diameter $3$ or $4$.

######  Proposition 8.2.

Let $\Gamma$ be a non-geometric distance-regular graph with
$D=3,~{}\theta_{D}\geq-3$ and $k\geq 2a_{1}+3\geq 91$. If $\Gamma$ contains an
induced quadrangle, then $a_{1}<100$.

###### Proof.

We first mention that if $a_{1}\geq 44$, then $c_{2}\geq\frac{a_{1}+6}{5}$ and
$k\leq\frac{13a_{1}+28}{5}\leq\frac{8}{3}(a_{1}+1)$. It is easy to see that
$k_{2}=k\cdot\frac{b_{1}}{c_{2}}\leq
k\cdot\frac{\frac{1}{5}(13a_{1}+28)-(a_{1}+1)}{\frac{1}{5}(a_{1}+6)}<k\cdot\frac{8(a_{1}+3)}{a_{1}+6}<8k$.

When $\gamma^{2}\geq 1$, by Lemma 7.3 we have
$k_{3}=k_{2}\cdot\frac{b_{2}}{c_{3}}\leq
k_{2}\cdot\frac{\frac{1}{2}(b_{1}+1)}{\frac{2}{5}(a_{1}+1)}\leq
k_{2}\cdot\frac{8a_{1}+28}{4(a_{1}+1)}<17k$, and hence
$\zeta-1=\frac{k_{2}+k_{3}}{k}<25$. Also $N\leq\frac{1}{0.956}$ and
$\delta\leq\frac{8}{3}$, and thus by Lemma 8.1 we obtain $a_{1}<69$.

When $\gamma^{2}<1$, we have $\min\\{a_{1}+1,a_{3}\\}\leq\theta_{1}<a_{1}+1$
from [25, Lemma 6]. This implies $a_{3}\leq a_{1}$ and then $c_{3}\geq
b_{1}+1$. So we have $k_{3}=k_{2}\cdot\frac{b_{2}}{c_{3}}\leq
k_{2}\cdot\frac{\frac{1}{2}(b_{1}+1)}{c_{3}}\leq\frac{1}{2}k_{2}$. Note also
that $\gamma^{2}\geq\frac{1}{5}$, since otherwise we have
$\frac{b_{1}}{2}-1<\theta_{1}<\frac{\sqrt{5}}{5}(a_{1}+1)<\frac{9}{20}(a_{1}+1)$,
and then we obtain $k<1.9a_{1}+3.9<2a_{1}+3$ as $a_{1}\geq 44$, which
contradicts our assumptions. We have therefore reduced to the case
$\frac{1}{5}\leq\gamma^{2}<1$.

If $\frac{1}{3}\leq\gamma^{2}<1$, we see that
$k_{2}<8k,~{}k_{3}\leq\frac{1}{2}k_{2}<4k$. Hence
$\zeta-1=\frac{k_{2}+k_{3}}{k}<12$. By Lemma 8.1 and $\delta\leq\frac{8}{3}$,
it follows that $a_{1}<100$.

If $\frac{1}{4}\leq\gamma^{2}<\frac{1}{3}$, it follows that
$\theta_{1}<\frac{\sqrt{3}}{3}(a_{1}+1)<\frac{3}{5}(a_{1}+1)$. As
$\frac{b_{1}}{2}-1<\theta_{1}$, we obtain that
$b_{1}<\frac{6a_{1}+16}{5}<\frac{5}{4}(a_{1}+1)$. Hence
$k<\frac{9}{4}(a_{1}+1)$, and then $\delta<\frac{9}{4}$. In this case we have
$k_{2}=k\cdot\frac{b_{1}}{c_{2}}<k\cdot\frac{\frac{1}{5}(6a_{1}+16)}{\frac{1}{5}(a_{1}+6)}<6k$
and $k_{3}\leq\frac{1}{2}k_{2}<3k$, so $\zeta-1=\frac{k_{2}+k_{3}}{k}<9$ and
thus $a_{1}<84$.

If $\frac{1}{5}\leq\gamma^{2}<\frac{1}{4}$, we find that
$\frac{b_{1}}{2}-1<\theta_{1}<\frac{1}{2}(a_{1}+1)$. This implies that
$k<2a_{1}+4$, and so $k=2a_{1}+3$. By [31, Proposition 9.5] we have
$c_{2}\geq\frac{3(a_{1}+1)-(2a_{1}+3)}{3}+1>\frac{a_{1}+2}{3}$, and then we
obtain
$k_{2}=k\cdot\frac{b_{1}}{c_{2}}<k\cdot\frac{a_{1}+2}{\frac{1}{3}(a_{1}+2)}=3k$
and $k_{3}\leq\frac{1}{2}k_{2}<1.5k$. Hence $\zeta-1<4.5$. Also $\delta<2.03$
as $a_{1}\geq 44$. By Lemma 8.1 it follows that $a_{1}<47$.

This proves the proposition. ∎

######  Proposition 8.3.

Let $\Gamma$ be a non-geometric distance-regular graph with
$D=4,~{}\theta_{D}\geq-3$ and $k\geq 2a_{1}+3\geq 91$. If $\Gamma$ contains an
induced quadrangle, then $a_{1}<100$.

###### Proof.

The proof is similar to that of Proposition 8.3. If $a_{1}\geq 44$, we obtain
that $c_{2}\geq\frac{a_{1}+6}{5}$ and
$k\leq\frac{13a_{1}+28}{5}\leq\frac{8}{3}(a_{1}+1)$. Also
$b_{1}=k-a_{1}-1\leq\frac{8a_{1}+23}{5}$,
$b_{2}\leq\frac{1}{2}(b_{1}+1)\leq\frac{4a_{1}+14}{5}$, $c_{3}\geq
b_{3}+2c_{2}-2\geq c_{1}+2c_{2}-2\geq\frac{2a_{1}+7}{5}$ and $c_{4}\geq
c_{3}-b_{3}+a_{1}+2\geq 2c_{2}+a_{1}\geq\frac{7a_{1}+12}{5}$ by Lemma 7.1 and
Lemma 7.3.

It is easy to show that $k_{2}=k\cdot\frac{b_{1}}{c_{2}}<8k$,
$k_{3}=k_{2}\cdot\frac{b_{2}}{c_{3}}\leq 2k_{2}<16k$ and
$k_{4}=k_{3}\cdot\frac{b_{3}}{c_{4}}\leq k_{3}\cdot\frac{b_{2}}{c_{4}}\leq
k_{3}\cdot\frac{4a_{1}+14}{7a_{1}+12}<10k$. Hence
$\zeta-1=\frac{k_{2}+k_{3}+k_{4}}{k}<34$. Note that when $D=4$ we have
$\gamma^{2}\geq 1$ by Lemma 3.3. Also $N\leq\frac{1}{0.956}$ and
$\delta\leq\frac{8}{3}$, and thus by Lemma 8.1 we obtain $a_{1}<94$. ∎

##  9 Computational results

In this section, with the aid of computer, we will find all the feasible
arrays for non-geometric distance-regular graphs with an induced quadrangle,
smallest eigenvalue at least $-3$, and diameter $3$ or $4$ whose $a_{1}$
satisfies the bounds in Propositions 8.2 and 8.3. To be precise, by ”feasible”
we mean that the intersection array
$\\{k=b_{0},b_{1},\ldots,b_{D-1};1=c_{1},c_{2},\ldots,c_{D}\\}$ satisfies the
following criteria.

  1. 1.

$1\leq a_{1}<100$ (see Section 8).

  2. 2.

$2a_{1}+3\leq k\leq 3a_{1}-2c_{2}+8$ (see Section 7).

  3. 3.

$k_{i}=\frac{b_{0}b_{1}\cdots b_{i-1}}{c_{1}c_{2}\cdots c_{i}}$ are all
integers, and $k_{i}a_{i}$ is even for $i\in\\{1,\ldots,D\\}$ (this is the
handshake lemma applied to the subgraphs induced on $\Gamma_{i}(x)$).

  4. 4.

$\min\\{\frac{a_{1}+6}{5},\frac{a_{1}+2}{4}\\}\leq
c_{2}\leq\frac{3a_{1}+8-k}{2}$ (see Section 7).

  5. 5.

The $b$’s are nonincreasing and $c$’s are nondecreasing, and all are between
$1$ and $k$. Furthermore, $b_{i}\geq c_{D-i}$ for all $i\in\\{1,\ldots,D\\}$
(see Section 2).

  6. 6.

For all $i\in\\{1,\ldots,D\\}$, we have $c_{i}-b_{i}\geq
c_{i-1}-b_{i-1}+a_{1}+2$ (this is an inequality due to Terwilliger; see Lemma
7.1).

  7. 7.

$2c_{2}-1\leq c_{3}$. (this is a consequence of Lemma 7.3)

  8. 8.

$3(a_{1}+3)(a_{2}+3)-3b_{1}c_{2}>0$ (this follows by applying Lemma 3.6 to the
$3\times 3$ principal submatrix of the matrix $L+3I$, where $L$ is defined in
Section 3).

  9. 9.

For $D=3$, we have $\frac{b_{1}}{2}-1<\theta_{1}<b_{1}-1$ (this lower bound
for $\theta_{1}$ is due to the main result in [27], while the upper bound is
due to [7, Theorem 4.4.3(ii) and Theorem 4.4.11], using the fact that we have
an induced quadrangle).

  10. 10.

The multiplicity $m_{i}$ of eigenvalue $\theta_{i}$ is a positive integer for
$i=0,1,\cdots,D$.

  11. 11.

For $D=3$, we have that at least one of the non-trivial eigenvalues is an
integer (this is because roots to the characteristic polynomials must occur in
algebraic conjugate pairs).

  12. 12.

Any pair of eigenvalues which are algebraic conjugates must have the same
multiplicity.

The python code used to determine these intersection arrays is available with
the arxiv submission of this paper.

###  9.1 Diameter 3

With these requirements, the code found the following feasible intersection
arrays:

  1. (1)

$\\{6,4,1;1,1,6\\}$;

  2. (2)

$\\{7,4,1;1,2,7\\}$;

  3. (3)

$\\{9,6,1;1,2,9\\}$;

  4. (4)

$\\{15,8,1;1,4,15\\}$;

  5. (5)

$\\{15,10,1;1,2,15\\}$;

  6. (6)

$\\{18,12,1;1,2,18\\}$;

  7. (7)

$\\{27,16,1;1,4,27\\}$;

  8. (8)

$\\{39,24,1;1,4,39\\}$;

  9. (9)

$\\{45,26,3;1,6,39\\}$;

  10. (10)

$\\{45,24,1;1,8,45\\}$;

  11. (11)

$\\{45,24,2;1,10,36\\}$;

  12. (12)

$\\{51,30,1;1,6,51\\}$;

  13. (13)

$\\{60,35,9;1,6,42\\}$;

  14. (14)

$\\{87,48,1;1,12,87\\}$;

  15. (15)

$\\{207,120,1;1,20,207\\}$.

Array $(1)$ has $c_{2}=1$, and has therefore been eliminated in Section 4.

For array $(2)$, we know it is the Klein graph and it fits in with our
requirements.

For array $(3)$, we find this array is the case $\\{st,s(t-1),1;1,t-1,st\\}$
when $s=3,t=3$. By [7, Proposition 12.5.2], we know this graph derived from a
strongly regular graph of parameters $(40,12,2,4)$ with a partition
$\mathfrak{S}$ of its point set into $4$-cliques. By [30], we know there are
$28$ non-isomorphic strongly regular graphs with parameters $(40,12,2,4)$.
Among those cases we know $GQ(3,3)$ minus a unique spread is eliminated since
it is geometric. But there is also a strongly regular graph that is not
geometric and it has 4 different spreads. The spreads come in pairs and give
two non-isomorphic distance-regular graphs that are non-geometric.

For $(4)$, the spectrum is $\\{[15]^{1},[5]^{12},[-1]^{15},[-3]^{20}\\}$.
Since the multiplicity of $5$ is $12<15$ and
$\frac{b_{1}}{\theta_{1}+1}=\frac{8}{6}$ is not integral, by [7, Theorem
4.4.4] it follows that this graph does not exist.

For array $(5)$, we find this array is the case $\\{st,s(t-1),1;1,t-1,st\\}$
when $s=5,t=3$. Similarly, we know this graph derived from a strongly regular
graph of parameters $(96,20,4,4)$ with a partition $\mathfrak{S}$ of its point
set into $6$-cliques. By [9, Section 7.2], we know that they are $GQ(5,3)$
minus a spread and an antipodal $6$-cover of $K_{16}$. The first one is
geometric and the second one is not. From that paper, we also know there
exists a non-geometric distance-regular graph derived from the collinearity
graph of $GQ(5,3)$.

For $(6)$, we find this array is the case $\\{st,s(t-1),1;1,t-1,st\\}$ when
$s=6,t=3$. We know this graph derived from a strongly regular graph of
parameters $(133,24,5,4)$ with a partition $\mathfrak{S}$ of its point set
into $7$-cliques. By [13] we know that $GQ(6,3)$ does not exist. However,
since the classification of strongly regular graph with parameters
$(133,24,5,4)$ is still pending, we do not know if there exist some non-
geometric cases with this intersection array by now.

For array $(7)$, we find the spectrum is
$\\{[27]^{1},[9]^{28},[-1]^{27},[-3]^{84}\\}$ and $a_{3}=0$, then it only can
be some distance-regular antipodal $5$-cover. Since the multiplicity of $9$ is
$28<27+5-2$ and $\frac{b_{1}}{\theta_{1}+1}=\frac{16}{10}$ is not integral, by
[18, Theorem 3] it follows that this graph does not exist.

For array $(8)$, the graph in question has been eliminated by [2, Proposition
5.20].

Array $(9)$ can be eliminated, as follows. The corresponding graph, if it
existed, would have $1+45+195+15=256$ vertices. It would not be bipartite,
since $-45$ is not an eigenvalue, and it is also not antipodal because
$a_{3}>0$. As such, the graph would be primitive, and therefore its
intersection array would be found in the tables in [7, Chapter 14]; however
this array does not appear there, and therefore the graph does not exist.

We can also eliminate array $(10)$, as follows. The spectrum of a graph with
this intersection array can be calculated as
$\\{[45]^{1},[15]^{23},[-1]^{45},[-3]^{115}\\}$. Since the multiplicity of the
eigenvalue $\theta_{1}=15$ is less than $k=45$, by [7, Theorem 4.4.4] we must
have $\theta_{1}+1=16$ dividing $b_{1}=24$, a contradiction. Thus no graph
with this intersection array can exist.

The remaining cases $(11)$-$(15)$ can all be eliminated in the same manner as
case $(10)$. The following table lists the intersection arrays and their
corresponding spectra. The reader may check that, in each case, $\theta_{1}$
has multiplicity less than $k$, and that $\theta_{1}+1$ does not divide
$b_{1}$. Therefore no graphs with these arrays can exist by [7, Theorem
4.4.4].

Intersection array | Spectrum
---|---
$\\{45,24,2;1,10,36\\}$ | $\\{[45]^{1},[15]^{16},[5]^{18},[-3]^{125}\\}$
$\\{51,30,1;1,6,51\\}$ | $\\{[51]^{1},[17]^{39},[-1]^{51},[-3]^{221}\\}$
$\\{60,35,9;1,6,42\\}$ | $\\{[60]^{1},[24]^{35},[6]^{50},[-3]^{400}\\}$
$\\{87,48,1;1,12,87\\}$ | $\\{[87]^{1},[29]^{33},[-1]^{87},[-3]^{319}\\}$
$\\{207,120,1;1,20,207\\}$ | $\\{[207]^{1},[69]^{52},[-1]^{207},[-3]^{1196}\\}$

From the discussion above, we can now summarize the computational results.

######  Proposition 9.1.

Let $\Gamma$ be a non-geometric distance-regular graph with smallest
eigenvalue $-3\leq\theta_{\min}<-2,c_{2}\geq 2,D=3$ and contains an induced
quadrangle, then $\Gamma$ is one of the following:

  * •

the Klein graph with $\iota(\Gamma)=\\{7,4,1;1,2,7\\}$;

  * •

a distance-regular graph with $\iota(\Gamma)=\\{9,6,1;1,2,9\\}$;

  * •

a distance-regular graph with $\iota(\Gamma)=\\{15,10,1;1,2,15\\}$;

  * •

a putative distance-regular graph with $\iota(\Gamma)=\\{18,12,1;1,2,18\\}$.

###  9.2 Diameter 4

Remarkably, our code found no intersection arrays that fit our requirements in
the diameter 4 case.

##  10 Proof of Theorem 1.1

In this section, we will collect our results and present the proof of the main
theorem.

###### Proof.

Let $\Gamma$ be a non-geometric distance-regular graph with diameter at least
3 and the smallest eigenvalue $\theta_{\min}$ satisfies
$-3\leq\theta_{\min}<-2$. First we consider the case $c_{2}=1$. They are
classified in Corollary 4.3 and Corollary 4.4 and we obtain the graphs of
$(a)-(i)$. So now we may assume $c_{2}\geq 2$. If $\Gamma$ has no induced
quadrangle then they are classified in Corollary 6.2 and we obtain the graphs
$(j)-(k)$. From now on we may assume that $\Gamma$ contains a quadrangle.
Koolen and Park [26] showed that a distance-regular graph with diameter at
least 3 and $k\leq 2a_{1}+2$ is a line graph, a Taylor graph, the Johnson
graph $J(7,3)$ or the halved 7-cube. The Johnson graph $J(7,3)$ is geometric,
line graphs have smallest eigenvalue at least $-2$ and the non-geometric
Taylor graphs are classified in Proposition 5.1. From this we obtain the
graphs $(l)-(n)$. So we may assume from now that $k\geq 2a_{1}+3$ and $k\leq
3a_{1}-2c_{2}+8\leq 3a_{1}+4$. In Proposition 7.7 we showed that $\Gamma$ must
have diameter at most 4. In Propositions 8.2 and 8.3 we obtain that such a
graph must have $a_{1}<100$. Then we found in Sections 9.1 and 9.2 the
remaining intersection arrays. This finishes the proof. ∎

##  11 Acknowledgements

The authors would like to thank Edward Spence and Junming Wang for valuable
conversations. J.H. Koolen is partially supported by the National Key R. and
D. Program of China (No. 2020YFA0713100), the National Natural Science
Foundation of China (No. 12071454 and No. 12371339), and the Anhui Initiative
in Quantum Information Technologies (No. AHY150000). Xiaoye Liang is partially
supported by the National Natural Science Foundation of China (No. 12201008
and No. 12371339), the foundation of Anhui Jianzhu University (No. 2022QDZ18),
the innovation team of operation research and combinatorial optimization of
Anhui province (No. 2023AH010020).

## References

  * [1] S. Bang.  Geometric distance-regular graphs without $4$-claws.  Linear Algebra Appl., 438:37–46, 2013.
  * [2] S. Bang, A. Gavrilyuk, and J. Koolen.  Distance-regular graphs without 4-claws.  European J. Combin., 80:120–142, 2019.
  * [3] S. Bang, A. Hiraki, and J. Koolen.  Improving diameter bounds for distance-regular graphs.  European J. Combin., 27(1):79–89, 2006.
  * [4] S. Bang and J. Koolen.  On geometric distance-regular graphs with diameter three.  European J. Combin., 36:331–341, 2014.
  * [5] N. Biggs, A. Boshier, and J. Shawe-Taylor.  Cubic distance-regular graphs.  J. London Math. Soc., S2-33(3):385–394, 1986.
  * [6] R. Bose.  Strongly regular graphs, partial geometries and partially balanced designs.  Pacific J. Math., 13:389–419, 1963.
  * [7] A. Brouwer, A. Cohen, and A. Neumaier.  Distance-Regular Graphs.  Springer-Verlag, Berlin Heidelberg, 1989.
  * [8] A. Brouwer and J. Koolen.  The distance-regular graphs of valency four.  J. Algebraic Combin., 10(1):5–24, 1999.
  * [9] A. Brouwer, J. Koolen, and M. Klin.  A root graph that is locally the line graph of the Petersen graph.  Discrete Math., 264(1):13–24, 2003.
  * [10] A. Brouwer and H. van Maldeghem.  Strongly Regular Graphs.  Cambridge University Press, 2022.
  * [11] P. Cameron, J. Goethals, J. Seidel, and E. Shult.  Line graphs, root systems and elliptic geometry.  J. Algebra, 43:305–327, 1976.
  * [12] P. Delsarte.  An algebraic approach to the association schemes of coding theory.  Philips Res. Reports Suppl., 10, 1973.
  * [13] S. Dixmier and F. Zara.  Essai d’une méthode d’étude de certains graphes lies aux groupes classiques.  Comptes Rendus Hebdomadaires des Séances de l’Académie des Sciences, Série A, pages 259–262, 1976.
  * [14] D. Fon-Der-Flaass.  A distance-regular graph with intersection array $\\{5,4,3,3;1,1,1,2\\}$ does not exist.  J. Algebraic Combin., 2(1):49–56, 1993.
  * [15] D. Fon-Der-Flaass.  There exists no distance-regular graph with intersection array $\\{5,4,3;1,1,2\\}$.  European J. Combin., 14:409–412, 1993.
  * [16] A. Gavrilyuk and A. Makhnev.  Distance-regular graph with the intersection array $\\{45,30,7;1,2,27\\}$ does not exist.  Discrete Math. Appl., 23:225–244, 2013.
  * [17] C. Godsil.  Geometric distance-regular covers.  New Zealand J. Math., 22(2):31–38, 1993.
  * [18] C. Godsil and J. Koolen.  On the multiplicity of eigenvalues of distance-regular graphs.  Linear Algebra Appl., pages 273–275, 1995.
  * [19] W. Haemers.  Interlacing eigenvalues and graphs.  Linear Algebra Appl., 226:593–616, 1995.
  * [20] A. Hiraki.  Distance-regular subgraphs in a distance-regular graph, III.  European J. Combin., 17(7):629–636, 1996.
  * [21] A. Hiraki, K. Nomura, and H. Suzuki.  Distance-regular graphs of valency 6 and $a_{1}=1$.  J. Algebraic Combin., 11(2):101–134, 2000.
  * [22] R. Horn and C. Johnson.  Matrix Analysis.  Cambridge University Press, 2012.
  * [23] J. Koolen and S. Bang.  On distance-regular graphs with smallest eigenvalue at least $-m$.  J. Combin. Theory Ser. B, 100(6):573–584, 2010.
  * [24] J. Koolen and B. Gebremichel.  There does not exist a strongly regular graph with parameters $(1911,270,105,27)$.  Electron. J. of Combin., pages P2–3, 2022.
  * [25] J. Koolen and J. Park.  Shilla distance-regular graphs.  European J. Combin., 31(8):2064–2073, 2010.
  * [26] J. Koolen and J. Park.  Distance-regular graphs with $a_{1}$ or $c_{2}$ at least half the valency.  J. Combin. Theory Ser. A, 119(3):546–555, 2012.
  * [27] J. Koolen, J. Park, and H. Yu.  An inequality involving the second largest and smallest eigenvalue of a distance-regular graph.  Linear Algebra Appl., 434:2404–2412, 2011.
  * [28] K. Metsch.  A characterization of Grassmann graphs.  European J. Combin., 16(6):639–644, 1995.
  * [29] J. Park.  The distance-regular graphs with valency $k\geq 2$, diameter $d\geq 3$ and $k_{D-1}+k_{D}\leq 2k$.  Discrete Math., 340:550–561, 2017.
  * [30] E. Spence.  The strongly regular $(40,12,2,4)$ graphs.  Electron. J. Combin., 7:#R22, 2000.
  * [31] E. van Dam, J. Koolen, and H. Tanaka.  Distance-regular graphs.  Electron J. Combin., #DS22, 2016.