# Recent progress on graphs with fixed smallest eigenvalue

Jack H. Koolen  School of Mathematical Sciences, University of Science and
Technology of China, 96 Jinzhai Road, Hefei, 230026, Anhui, PR China. CAS Wu
Wen-Tsun Key Laboratory of Mathematics, University of Science and Technology
of China, 96 Jinzhai Road, Hefei, Anhui, 230026, PR China  Meng-Yue Cao
School of Mathematical Sciences, Beijing Normal University, 19 Xinjiekouwai
Street, Beijing, 100875, PR China.  Qianqian Yang111Corresponding author.
School of Mathematical Sciences, University of Science and Technology of
China, 96 Jinzhai Road, Hefei, 230026, Anhui, PR China.

###### Abstract

We give a survey on graphs with fixed smallest eigenvalue, especially on
graphs with large minimal valency and also on graphs with good structures. Our
survey mainly consists of the following two parts:

  1. (i)

Hoffman graphs, the basic theory related to Hoffman graphs and the
applications of Hoffman graphs to graphs with fixed smallest eigenvalue and
large minimal valency;

  2. (ii)

recent results on distance-regular graphs and co-edge regular graphs with
fixed smallest eigenvalue and the characterizations of certain families of
distance-regular graphs.

At the end of the survey, we also discuss signed graphs with fixed smallest
eigenvalue and present some new findings.

††2010 Mathematics Subject Classification. Primary 05C50. Secondary 05C22,
05C75, 05E30, 05D99, 11H06.††E-mail addresses<EMAIL_ADDRESS>(J.H.
Koolen<EMAIL_ADDRESS>(M.-Y. Cao<EMAIL_ADDRESS>(Q. Yang).

##  1 Introduction

All graphs mentioned in this paper are finite, undirected and simple. For
undefined notations see [13], [35] and [43]. Unless we specify a different
matrix, by an eigenvalue of a graph, we mean an eigenvalue of its adjacency
matrix. Note that as the adjacency matrix of a graph is a symmetric real
matrix, it is diagonalizable and all its eigenvalues are real.

In this paper, we mainly study the smallest eigenvalue of a graph. One of the
oldest results is that for a connected graph, its smallest eigenvalue is in
absolute value at most the largest eigenvalue and equality holds if and only
if this graph is bipartite (see [13, Proposition 3.1.1, Proposition 3.4.1]).
This is a consequence of the Perron-Frobenius Theorem.

An important result by Hoffman gives a bound on the stability number $\alpha$
of a $k$-regular graph $G$ with order $n$ and smallest eigenvalue
$\lambda_{\min}(G)$ as follows:

$\alpha\leq\frac{n}{1+\frac{k}{-\lambda_{\min}(G)}}$

(unpublished; see [13, Theorem 3.5.2]). We call this bound the _Hoffman bound_
or the _ratio bound_. This bound has many applications, for example in
extremal combinatorics. Godsil and Meagher [42] used this bound to show many
Erdős-Ko-Rado theorems. This bound also gives a lower bound on the chromatic
number $\chi$ of $G$, that is $\chi\geq 1+\frac{k}{-\lambda_{\min}(G)}$, as
each color class of $G$ is a stable set.

Recently, Bramoullé, Kranton and D’Amours [11] have shown that the equilibria
of many economic systems only depend on the smallest eigenvalue of the
underlying network.

The main topic of this paper is to survey the area of graphs with fixed
smallest eigenvalue. In Section 2, we describe the classical $1976$ result of
Cameron, Goethals, Seidel and Shult [15] characterizing graphs with smallest
eigenvalue at least $-2$ and the corresponding $2018$ result of Koolen, Yang
and Yang [62] for graphs with smallest eigenvalue at least $-3$. Also in this
section, we present two classical results of Hoffman and related results by
Woo and Neumaier [94], Yu [97] and Aharoni, Alon and Berger [1]. The first
result of Hoffman [49] shows the following: Let $G$ be a graph with smallest
eigenvalue $\lambda_{\min}(G)$ and large minimal valency. If
$\lambda_{\min}(G)>-2$, then $\lambda_{\min}(G)=-1$ and $G$ is a disjoint
union of cliques; if $\lambda_{\min}(G)>-1-\sqrt{2}$, then
$\lambda_{\min}(G)=-2$ and $G$ is a generalized line graph. The second result
of Hoffman [48] shows that the smallest eigenvalue of a graph depends very
much on its local structure. For recent surveys on graphs with smallest
eigenvalue at least $-2$, we refer to Cvetković, Rowlinson and Simić [33] and
[34]. In Section 3, we define Hoffman graphs and present the basic theory of
Hoffman graphs. In Section 4, we investigate graphs with bounded smallest
eigenvalue and large minimal valency. In Section 5 we discuss distance-regular
graphs. We look at distance-regular graphs with fixed smallest eigenvalue and
also at characterizations of certain families of distance-regular graphs. In
Section 6 we discuss co-edge regular graphs. In Section 7 we explore signed
graphs and Seidel matrices. In Section 8, we give several problems on unsigned
and signed graphs. In Appendix A, we define $Q$-polynomial distance-regular
graphs and their Terwilliger algebra.

Note that if a regular graph $G$ has smallest eigenvalue $\lambda_{\min}(G)$,
then its complement $\overline{G}$ is also regular with second largest
eigenvalue $-\lambda_{\min}(G)-1$. Henceforth we scratch the area of regular
graphs with fixed second largest eigenvalue.

###  1.1 Regular graphs with fixed second largest eigenvalue

There is a tremendous amount of literature about regular graphs with fixed
second largest eigenvalue. In this subsection, we give some highlights of this
area, but we do not intend to survey the area. One of the reasons is that the
area has quite a bit of different flavors from the rest of this paper, and
another is that there is so much literature that probably will make a small
book. We follow [13, Chapter 4]. For more details, see also that chapter.

An expander is a (preferably sparse) graph with the property that the number
of vertices at distance at most $1$ from any given (not too large) set $S$ of
vertices is at least a fixed constant $(>1)$ times the size of $S$. Expanders
became famous, because of their role in sorting networks (cf. Ajtai, Komlós
and Szemerédi [2]). For a recent survey on expanders, see [51].

Let $G$ be a connected $k$-regular graph with distinct eigenvalues
$k>\lambda_{1}>\cdots>\lambda_{t}$. Let
$\lambda:=\max\\{\lambda_{1},-\lambda_{t}\\}$. It is shown in [13, Proposition
4.3.1, Proposition 4.5.1], also in [4], that if the ratio $\frac{k}{\lambda}$
is larger, then the expansion properties of $G$ are better. Also if the ratio
$\frac{k}{\lambda}$ is large, then the graph has good connectivity and
randomness properties. For a survey on pseudo-random graphs, that is, graphs
with good randomness properties, see [66].

A theorem by Alon and Boppana shows that the second largest eigenvalue of a
$k$-regular graph can not be much smaller than $2\sqrt{k-1}$.

######  Theorem 1.1 ([3, Alon-Boppana]).

Let $k\geq 3$ be an integer. There exists a positive constant $C$ such that
the second largest eigenvalue $\lambda_{1}$ of a $k$-regular graph of order
$n$ satisfies

$\lambda_{1}\geq\sqrt{k-1}(1-C\frac{\ln{(k-1)}}{\ln{n}}).$

Serre [80] has shown that for a $k$-regular graph, many of its eigenvalues are
not much smaller than $2\sqrt{k-1}$.

######  Theorem 1.2.

Fix $k\geq 1$. For each $\varepsilon>0$, there exists a positive constant
$c=c(k,\varepsilon)$ such that for any $k$-regular graph $G$ of order $n$, the
number of eigenvalues larger than $(2-\varepsilon)\sqrt{k-1}$ is at least
$cn$.

There are many improvements and generalizations of the above two theorems with
applications to coding theory and other areas, see for example [30], [50] and
[69].

Alon [3] conjectured that for fixed $k,\varepsilon>0$ and $n$ sufficiently
large, a random $k$-regular graph of order $n$ has second largest eigenvalue
at most $2\sqrt{k-1}+\varepsilon$. This conjecture was shown to be true by
Friedman [36].

These results show that the above mentioned ratio $\frac{k}{\lambda}$ can not
be much larger than $\frac{k}{2\sqrt{k-1}}$. This leads us to define Ramanujan
graphs. A Ramanujan graph is a connected $k$-regular graph such that any
eigenvalue $\lambda\neq\pm k$ satisfies $|\lambda|\leq 2\sqrt{k-1}$. Complete
graphs are Ramanujan graphs. Note that a sparse non-bipartite Ramanujan graph
is a particular good expander. It is of very great interest to construct
infinite families of Ramanujan graphs with fixed valency $k$ and unbounded
number of vertices. There are several constructions known of infinite families
of non-bipartite Ramanujan graphs, for example, by Lubotzky, Phillips and
Sarnak [70], Margulis [72] and Morgenstern [75], but they are only known for
particular $k$. Recently, Marcus, Spielman and Srivastava [71] found for every
$k\geq 3$ an infinite family of bipartite Ramanujan graphs with valency $k$
and unbounded number of vertices. It still remains an open problem to
construct infinite families of non-bipartite $k$-regular Ramanujan graphs for
all of $k\geq 3$.

##  2 An overview of the main results

In this section, we give an overview of the main results in the area of graphs
with fixed smallest eigenvalue. At the beginning of this section, we introduce
some basic terminology.

Let $G$ be a graph with _vertex set_ $V(G)$ and _edge set_
$E(G)\subseteq\binom{V(G)}{2}$, where $V(G)$ is a finite set. If $\\{x,y\\}$
is in $E(G)$, then we say that $x$ and $y$ are _neighbors_ or $x$ and $y$ are
_adjacent_ and write $x\sim y$ in this case. We say that a vertex $x$ is
_incident_ with an edge $e$ if $x\in e$.

The _adjacency matrix_ $A(G)$ of a graph $G$ is the square $(0,1)$-matrix with
rows and columns are indexed by $V(G)$, such that the $(x,y)$-entry of $A(G)$
is $1$ if and only if $x$ and $y$ are adjacent. As $A(G)$ is a symmetric
matrix, all its eigenvalues are real. The _eigenvalues_ of $G$ are just the
eigenvalues of $A(G)$. We call the multiset of eigenvalues of $G$ with their
multiplicities the _spectrum_ of $G$. We call two graphs _cospectral_ if they
have the same spectrum. In this paper, we are mainly interested in the
smallest eigenvalue of $G$, which is denoted by $\lambda_{\min}(G)$.

###  2.1 $s$-Integrability of graphs

Let $\Sigma$ be a finite set of vectors in $\mathbb{R}^{n}$. The lattice
$\Lambda$ generated by $\Sigma$ is defined as

$\Lambda:=\left\\{\sum_{\mathbf{v}\in\Sigma}\alpha_{\mathbf{v}}\mathbf{v}\mid\alpha_{\mathbf{v}}\in\mathbb{Z}\text{
for all }\mathbf{v}\in\Sigma\right\\},$

and denoted by $\langle\Sigma\rangle_{\mathbb{Z}}$. The lattice $\Lambda$ is
called integral, if the standard inner product
$(\mathbf{v}_{1},\mathbf{v}_{2})$ is integral for all
$\mathbf{v}_{1},\mathbf{v}_{2}\in\Sigma$. Let $Gr(\Sigma)$ be the matrix with
rows and columns are indexed by the set $\Sigma$, such that the
$(\mathbf{v}_{1},\mathbf{v}_{2})$-entry of $Gr(\Sigma)$ is
$(\mathbf{v}_{1},\mathbf{v}_{2})$. Note that the lattice $\Lambda$ is integral
if and only if the matrix $Gr(\Sigma)$ is an integral matrix.

Following Conway and Sloane [31], we say that an integral lattice $\Lambda$ is
$s$-integrable (for some positive integer $s$) if $\sqrt{s}\Lambda$ is a
sublattice of a standard lattice, which is a lattice generated by a set of
orthonormal vectors. This is equivalent with the condition that
$sGr(\Sigma)=N^{T}N$ holds for some integral matrix $N$.

Let $G$ be a graph with $A(G)$ as its adjacency matrix. Then the matrix
$B(G):=A(G)+\lceil-\lambda_{\min}(G)\rceil I$ is positive semidefinite and
hence can be written as $B(G)=M^{T}M$ for some real matrix $M$. Denote by
$\Lambda(G)$ the lattice generated by the columns of $M$. Note that the
isomorphism class of $\Lambda(G)$ only depends on $B(G)$, not on $M$. For a
positive integer $s$, we say that the graph $G$ is _$s$ -integrable_ if the
lattice $\Lambda(G)$ is $s$-integrable, or equivalently, $sB(G)=N^{T}N$ holds
for some integral matrix $N$. Note that if a graph $G$ is $s$-integrable and
$t$-integrable, then $G$ is $(s+t)$-integrable. So a $1$-integrable graph is
$s$-integrable for $s\geq 1$.

In 1976, Cameron et al. [15] showed the following result:

######  Theorem 2.1 (cf. [15, Theorem 4.3, Theorem 4.10]).

If $G$ is a connected graph with $\lambda_{\min}(G)\geq-2$, then $G$ is
$s$-integrable for any $s\geq 2$. Moreover, if $G$ has at least $37$ vertices,
then $G$ is $1$-integrable.

A graph is a _generalized line graph_ if it is $1$-integrable with smallest
eigenvalue at least $-2$. Let $G$ be a graph. The _line graph_ of $G$, denoted
by $L(G)$, is the graph with vertex set $E(G)$ such that edges $e$ and $f$ are
adjacent in $L(G)$ if there is a unique vertex $x$ incident with $e$ and $f$
in $G$. Let $N$ be the $|V(G)|\times|E(G)|$ $(0,1)$-matrix whose $(x,e)$-entry
equals $1$ if and only if the vertex $x$ is incident with the edge $e$. Then
$A(L(G))+2I=N^{T}N$. This means that $L(G)$ has smallest eigenvalue at least
$-2$ and is $1$-integrable. But for a generalized line graph $H$, if an
integral matrix $N^{\prime}$ satisfies $A(H)+2I=(N^{\prime})^{T}N^{\prime}$,
then $N^{\prime}$ is a $(0,\pm 1)$-matrix.

For more about graphs with smallest eigenvalue at least $-2$, we refer to [33]
and [34].

Later in 2018, Koolen et al. [62] studied the integrability of graphs with
smallest eigenvalue at least $-3$ and proved that:

######  Theorem 2.2 (cf. [62, Theorem 1.3]).

There exists a positive constant $\kappa_{1}$ such that, if $G$ is a graph
with $\lambda_{\min}(G)\geq-3$ and minimal valency at least $\kappa_{1}$, then
$G$ is $s$-integrable for any $s\geq 2$.

To prove the above theorem, they use Hoffman graphs as their main tool, which
will be introduced in the next section.

######  Remark 2.3.

  1. (i)

After Theorem 4.8, we give a sketch of the proof of Theorem 2.2.

  2. (ii)

It is known that $\kappa_{1}$ is at least $166$ by results of Koolen and
Munemasa [59] and Koolen, Rehman and Yang [61].

###  2.2 Two results of Hoffman

Hoffman [49] in 1977 showed the following related results.

######  Theorem 2.4 (cf. [49, Theorem 1.1]).

  1. (i)

For any real number $\lambda\in(-2,-1]$, there exists a constant
$C_{1}(\lambda)$ such that, if $G$ is a graph with
$\lambda_{\min}(G)\geq\lambda$ and minimal valency at least $C_{1}(\lambda)$,
then $\lambda_{\min}(G)=-1$ and $G$ is a disjoint union of cliques.

  2. (ii)

For any real number $\lambda\in(-1-\sqrt{2},-2]$, there exists a constant
$C_{1}(\lambda)$ such that, if $G$ is a graph with
$\lambda_{\min}(G)\geq\lambda$ and minimal valency at least $C_{1}(\lambda)$,
then $\lambda_{\min}(G)\geq-2$ and $G$ is a generalized line graph and hence
is $1$-integrable.

The second item of this theorem can be reformulated as follows:

######  Theorem 2.5 (cf. [12, Theorem 3.12.5]).

Let $\hat{\theta}_{k}$ be the supremum of the smallest eigenvalues of graphs
with minimal valency at least $k$ and smallest eigenvalue less than $-2$. Then
$\\{\hat{\theta}_{k}\\}_{k=1}^{\infty}$ forms a monotone decreasing sequence
with limit $-1-\sqrt{2}$.

Following the ideas of Hoffman, Woo and Neumaier [94] in 1995 showed that

######  Theorem 2.6 (cf. [94, Theorem 5.1]).

For any real number $\lambda\in(\alpha_{1},-1-\sqrt{2}]$, where
$\alpha_{1}\approx-2.4812$ is the smallest root of the polynomial
$x^{3}+2x^{2}-2x-2$, there exists a positive constant $C_{1}(\lambda)$ such
that, if $G$ is a graph with $\lambda_{\min}(G)\geq\lambda$ and minimal
valency at least $C_{1}(\lambda)$, then $\lambda_{\min}(G)\geq-1-\sqrt{2}$.

This theorem can also be reformulated as follows:

######  Theorem 2.7 ([97, Theorem 1.3]).

Let $\hat{\sigma}_{k}$ be the supremum of the smallest eigenvalues of graphs
with minimal valency at least $k$ and smallest eigenvalue less than
$-1-\sqrt{2}$. Then $\\{\hat{\sigma}_{k}\\}_{k=1}^{\infty}$ forms a monotone
decreasing sequence with limit $\alpha_{1}$, the smallest root of the
polynomial $x^{3}+2x^{2}-2x-2$.

######  Remark 2.8.

  1. (i)

Bussemaker and Neumaier [14] showed that $\hat{\theta}_{1}$ is the smallest
eigenvalue of the graph $E_{10}$ (for a picture see below) and this graph is
the unique connected graph with $\hat{\theta}_{1}$ as its smallest eigenvalue,
which is approximately $-2.006594$, the smallest root of the polynomial
$x^{2}(x^{2}-1)^{2}(x^{2}-3)(x^{2}-4)-1$.

$E_{10}$

  2. (ii)

Let $\hat{\eta}_{k}$ be the supremum of the smallest eigenvalues of
$k$-regular graphs with smallest eigenvalue less than $-2$. Then the limit of
the sequence $\\{\hat{\eta}_{k}\\}_{k=1}^{\infty}$ is $-1-\sqrt{2}$ (see
[97]).

  3. (iii)

Yu [97] also showed that $\hat{\eta}_{3}$ is the smallest eigenvalue of the
Yu-graph (for a picture see below) and this graph is the unique connected
$3$-regular graph with $\hat{\eta}_{3}$ as its smallest eigenvalue, which is
approximately $-2.0391$, the smallest root of the polynomial
$x^{6}-3x^{5}-7x^{4}+21x^{3}+13x^{2}-35x-4$.

Yu-graph

  4. (iv)

Let $\hat{\xi}_{k}$ be the supremum of the smallest eigenvalues of $k$-regular
graphs with smallest eigenvalue less than $-1-\sqrt{2}$. Then the limit of the
sequence $\\{\xi_{k}\\}_{k=1}^{\infty}$ is $\alpha_{1}$ (see [97]).

Now we look at graphs with a bounded smallest eigenvalue. In order to state
the results we need to introduce the graph $\widetilde{K}_{2t}$. Let $t$ be a
positive integer. Denote by $\widetilde{K}_{2t}$ the graph with $2t+1$
vertices consisting of a clique $K_{2t}$ together with a vertex that is
adjacent to exactly $t$ vertices of the clique. Note that the smallest
eigenvalue of $\widetilde{K}_{2t}$ goes to $-\infty$ as $t$ goes to $\infty$.
(For a proof, see [95, Lemma 3.2].) It is fairly easy to see that the smallest
eigenvalue of the $t$-claw $K_{1,t}$ also goes to $-\infty$ as $t$ goes to
$\infty$, as $\lambda_{\min}(K_{1,t})=-\sqrt{t}$.

Hoffman [48] in 1973 showed the following results:

######  Theorem 2.9 ([48, p. 278]).

  1. (i)

Let $\lambda$ be a positive real number. Then there exists a positive integer
$T=T(\lambda)$ such that, if $G$ is a graph with
$\lambda_{\min}(G)\geq-\lambda$, then $G$ contains neither $K_{1,T}$ nor
$\widetilde{K}_{2T}$ as an induced subgraph.

  2. (ii)

Let $t\geq 3$ be a positive integer. Then there exists a positive constant
$\lambda=\lambda(t)$ such that, if a graph $G$ does not contain $K_{1,t}$ and
$\widetilde{K}_{2t}$, then $\lambda_{\min}(G)\geq-\lambda$.

This theorem shows that the smallest eigenvalue of a graph is quite dependent
on the local information.

A related result is obtained by Aharoni et al. [1]. Before we state their
result we need to introduce the Laplacian matrix. For a graph $G$ on $n$
vertices, define its _Laplacian matrix_ $L(G)$ as follows:
$L(G)=\Delta(G)-A(G)$, where $\Delta(G)$ is the diagonal matrix with
$\Delta(G)_{x,x}=k_{G}(x)$, the valency of $x$ in $G$, and $A(G)$ is the
adjacency matrix of $G$. They obtained the following result:

######  Theorem 2.10 ([1, Theorem 1.1]).

Let $G$ be a graph with maximal valency $k$ containing no induced
$K_{1,\ell}$’s. Let $t(k,\ell)$ denote the minimum possible number of edges of
a graph on $k$ vertices with no stable set of size $\ell$. If $\theta$ is the
maximal eigenvalue of the Laplacian matrix of $G$, then $\theta\leq
2k-\frac{t(k,\ell)}{k-1}$.

It is known by Turán’s Theorem that $t(k,\ell)=(1+o(1))\frac{k^{2}}{2\ell-2}$,
where the $o(1)$-term tends to zero as $k$ tends to infinity.

For regular graphs, we obtain the following corollary:

######  Corollary 2.11.

Let $G$ be a $k$-regular graph containing no induced $K_{1,\ell}$’s. Then
$\lambda_{\min}(G)\geq-(1+o(1))\frac{2\ell-3}{2\ell-2}k$.

######  Proof.

This follows from Theorem 2.10 immediately. ∎

It is not clear whether the lower bound in Corollary 2.11 is the best bound on
the smallest eigenvalue of regular graphs. Here, given an integer $\ell\geq 2$
and a connected bipartite $(\ell-1)$-regular graph $G^{\prime}$, we are able
to construct an infinite family of regular graphs
$\\{G_{1},G_{2},\ldots,G_{s},\ldots\\}$ satisfying

  1. (i)

$G_{s}$ is $k_{s}$-regular and does not contain induced $K_{1,\ell}$’s, for
$s=1,2,\ldots$;

  2. (ii)

$k_{s}\rightarrow\infty$, as $s\rightarrow\infty$;

  3. (iii)

$\lim_{s\rightarrow\infty}\frac{\lambda_{\min}(G_{s})}{k_{s}}=-\frac{\ell-2}{\ell}$.

For this, we need to introduce the clique extension of a given graph. For a
positive integer $s$ and a graph $H$, the $s$-_clique extension_ of $H$ is the
graph $\widetilde{H}$ obtained from $H$ by replacing each vertex $x\in V(H)$
by a clique $\widetilde{X}$ with $s$ vertices, such that
$\tilde{x}\sim\tilde{y}$ (for
$\tilde{x}\in\widetilde{X},~{}\tilde{y}\in\widetilde{Y},~{}\widetilde{X}\neq\widetilde{Y}$)
in $\widetilde{H}$ if and only if $x\sim y$ in $H$. In particular, if $H$ has
spectrum

$\left\\{\lambda_{0}^{m_{0}},\lambda_{1}^{m_{1}},\ldots,\lambda_{t}^{m_{t}}\right\\},$
(1)

then $\widetilde{H}$ has spectrum

$\left\\{(s(\lambda_{0}+1)-1)^{m_{0}},(s(\lambda_{1}+1)-1)^{m_{1}},\ldots,(s(\lambda_{t}+1)-1)^{m_{t}},(-1)^{(m_{0}+m_{1}+\cdots+m_{t})}\right\\}$
(2)

(see [47, p. 107]).

Now we start our construction. For each $s$, let $G_{s}$ be the $s$-clique
extension of $G^{\prime}$. Then $G_{s}$ is regular with valency $k_{s}:=\ell
s-1$ and with smallest eigenvalue $\lambda_{\min}(G_{s}):=-\ell s+2s-1$. It is
not hard to check that these graphs $G_{s}$’s satisfy the above properties.

Let $\lambda_{\ell,k}:=\inf\left\\{\lambda_{\min}(G)\mid G\right.$ is
$k$-regular and does not contain induced $K_{1,\ell}$’s$\\}$ be a real number.
Consider

$\tau_{\ell}:=\inf\left\\{\frac{\lambda_{\ell,k}}{k}\mid
k=3,4,\ldots\right\\}.$

Corollary 2.10 and the above examples we constructed imply
$-\frac{2\ell-3}{2\ell-2}\leq\tau_{\ell}\leq-\frac{\ell-2}{\ell}$.

######  Problem 2.12.

Determine $\tau_{\ell}$ for all $\ell\geq 3$.

For the particular case where $\ell=3$, Cioabă, Elzinga and Gregory [28,
Theorem 4.5] proved $\lambda_{3,3}\geq\theta\approx-2.272$, where $\theta$ is
the smallest root of the polynomial $x^{3}+x+14$. Furthermore, for graphs
containing no induced $K_{1,3}$’s, that is, claw-free graphs, Chudnovsky and
Seymour [20, 21, 22, 23, 24, 25, 26, 27], developed a structure theory. This
may help to determine $\tau_{2}$.

##  3 Hoffman graphs

We describe now two methods used to study graphs with fixed smallest
eigenvalues. The first technique is the so-called Bose-Laskar method. In this
method, they use the fact that if a graph does not contain induced $t$-claws
with large $t$, then this graph must contain large cliques. This method works
best if there is some local regularity in the graph. The second method is to
use Hoffman graphs as a tool, which was introduced by Woo and Neumaier [94],
following ideas of Hoffman. This method gives more precise local information
of a graph than the Bose-Laskar method, but the disadvantage of this method is
that we need to assume that the minimal valency of graphs is very large, as we
need Ramsey theory to show the existence of large cliques. In this section we
discuss Hoffman graphs and give the basic theory for them.

######  Definition 3.1 (Hoffman graph).

A Hoffman graph $\mathfrak{h}$ is a pair $(H,\ell)$, where $H=(V,E)$ is a
graph and $\ell:V\to\\{f,s\\}$ is a labeling map satisfying the following
conditions:

  1. (i)

vertices with label $f$ are pairwise non-adjacent,

  2. (ii)

every vertex with label $f$ is adjacent to at least one vertex with label $s$.

We call a vertex with label $s$ a _slim vertex_ , and a vertex with label $f$
a _fat vertex_. We denote by $V_{\mathrm{slim}}(\mathfrak{h})$ (resp.
$V_{\mathrm{fat}}(\mathfrak{h})$) the set of slim (resp. fat) vertices of
$\mathfrak{h}$.

For a vertex $x$ of $\mathfrak{h}$, we define $N_{\mathfrak{h}}^{s}(x)$ (resp.
$N_{\mathfrak{h}}^{f}(x)$) the set of slim (resp. fat) neighbors of $x$ in
$\mathfrak{h}$. If every slim vertex of $\mathfrak{h}$ has a fat neighbor,
then we call $\mathfrak{h}$ _fat_ , and if every slim vertex of $\mathfrak{h}$
has at least $t$ fat neighbors, we call $\mathfrak{h}$ $t$-_fat_. In a similar
fashion, we define $N^{f}_{\mathfrak{h}}(x_{1},x_{2})$ to be the set of common
fat neighbors of two slim vertices $x_{1}$ and $x_{2}$ in $\mathfrak{h}$ and
$N^{s}_{\mathfrak{h}}(f_{1},f_{2})$ to be the set of common slim neighbors of
two fat vertices $f_{1}$ and $f_{2}$ in $\mathfrak{h}$.

The _slim graph_ of the Hoffman graph $\mathfrak{h}$ is the subgraph of $H$
induced on $V_{\mathrm{slim}}(\mathfrak{h})$. Note that any graph can be
considered as a Hoffman graph with only slim vertices, and vice versa. We will
not distinguish between Hoffman graphs with only slim vertices and graphs.

A Hoffman graph $\mathfrak{h}_{1}=(H_{1},\ell_{1})$ is called an (_proper_)
_induced Hoffman subgraph_ of $\mathfrak{h}=(H,\ell)$, if $H_{1}$ is an
(proper) induced subgraph of $H$ and $\ell_{1}(x)=\ell(x)$ holds for all
vertices $x$ of $H_{1}$.

Let $W$ be a subset of $V_{\mathrm{slim}}(\mathfrak{h})$. An induced Hoffman
subgraph of $\mathfrak{h}$ generated by $W$, denoted by $\langle
W\rangle_{\mathfrak{h}}$, is the Hoffman subgraph of $\mathfrak{h}$ induced on
$W\cup\\{f\in V_{\mathrm{fat}}(\mathfrak{h})\mid f\sim w\text{ for some }w\in
W\\}$.

For a fat vertex $f$ of $\mathfrak{h}$, a _quasi-clique_ (with respect to $f$)
is a subgraph of the slim graph of $\mathfrak{h}$ induced on the slim vertices
adjacent to $f$ in $\mathfrak{h}$, and we denote it by $Q_{\mathfrak{h}}(f)$.

######  Definition 3.2 (isomorphism of Hoffman graphs).

Two Hoffman graphs $\mathfrak{h}=(H,\ell)$ and
$\mathfrak{h}^{\prime}=(H^{\prime},\ell^{\prime})$ are isomorphic if there
exists an isomorphism from $H$ to $H^{\prime}$ which preserves the labeling.

######  Definition 3.3 (strong isomorphism of Hoffman graphs).

Two Hoffman graphs $\mathfrak{h}=(H,\ell)$ and
$\mathfrak{h}^{\prime}=(H^{\prime},\ell^{\prime})$ are strongly isomorphic if
they have the same set of slim vertices and there exists an isomorphism from
$\mathfrak{h}$ to $\mathfrak{h}^{\prime}$ which fixes the set of slim vertices
vertex-wise.

Note that if two Hoffman graphs are strongly isomorphic, then they have the
same slim graph.

######  Definition 3.4 (special matrix).

For a Hoffman graph $\mathfrak{h}=(H,\ell)$, there exists a matrix $C$ such
that the adjacency matrix $A$ of $H$ satisfies

$\displaystyle A=\left(\begin{array}[]{cc}A_{s}&C\\\
C^{T}&O\end{array}\right),$

where $A_{s}$ is the adjacency matrix of the slim graph of $\mathfrak{h}$. The
special matrix $Sp(\mathfrak{h})$ of $\mathfrak{h}$ is the real symmetric
matrix $A_{s}-CC^{T}.$

The _eigenvalues_ of $\mathfrak{h}$ are the eigenvalues of its special matrix
$Sp(\mathfrak{h})$, and the smallest eigenvalue of $\mathfrak{h}$ is denoted
by $\lambda_{\min}(\mathfrak{h})$. Note that $\mathfrak{h}$ is not determined
by its special matrix in general, since different $\mathfrak{h}$’s may have
the same special matrix. Observe also that if there are no fat vertices in
$\mathfrak{h}$, then $Sp(\mathfrak{h})=A_{s}$ is just the standard adjacency
matrix.

######  Lemma 3.5 ([94, Lemma 3.4]).

Let $\mathfrak{h}$ be a Hoffman graph and let $x_{i}$ and $x_{j}$ be two
distinct slim vertices of $\mathfrak{h}$. The special matrix
$Sp(\mathfrak{h})$ has diagonal entries

$Sp(\mathfrak{h})_{x_{i},x_{i}}=-|N_{\mathfrak{h}}^{f}(x_{i})|$

and off-diagonal entries

$Sp(\mathfrak{h})_{x_{i},x_{j}}=(A_{s})_{x_{i},x_{j}}-|N_{\mathfrak{h}}^{f}(x_{i},x_{j})|.$

For the smallest eigenvalues of Hoffman graphs and their induced Hoffman
subgraphs, Woo and Neumaier showed the following inequality.

######  Lemma 3.6 ([94, Corollary 3.3]).

If $\mathfrak{h}_{1}$ is an induced Hoffman subgraph of a Hoffman graph
$\mathfrak{h}$, then
$\lambda_{\min}(\mathfrak{h}_{1})\geq\lambda_{\min}(\mathfrak{h})$ holds.

As a corollary of Lemma 3.6, we have:

######  Lemma 3.7.

If $G_{1}$ is an induced subgraph of $G$, then
$\lambda_{\min}(G_{1})\geq\lambda_{\min}(G)$ holds.

######  Definition 3.8 ($\mu$-saturated Hoffman graph).

Let $\mu\leq-1$ be a real number and let $\mathfrak{h}$ be a Hoffman graph
with smallest eigenvalue at least $\mu$. Then $\mathfrak{h}$ is
$\mu$-saturated if no fat vertex can be attached to $\mathfrak{h}$ in such a
way that the resulting Hoffman graph has smallest eigenvalue at least $\mu$.

Now we introduce a result of Hoffman and Ostrowski. In order to state this, we
need to introduce the following notations. Suppose $\mathfrak{h}$ is a Hoffman
graph and $\\{f_{1},\dots,f_{r}\\}$ is a subset of
$V_{\mathrm{fat}}(\mathfrak{h})$. Let
$\mathfrak{g}^{n_{1},\ldots,n_{r}}(\mathfrak{h})$ be the Hoffman graph
obtained from $\mathfrak{h}$ by replacing the fat vertex $f_{i}$ by a slim
$n_{i}$-clique $K^{f_{i}}$, and joining all the neighbors of $f_{i}$ (in
$\mathfrak{h}$) with all the vertices of $K^{f_{i}}$ for all $i$. We will
write $G(\mathfrak{h},n)$ for the graph
$\mathfrak{g}^{n_{1},\ldots,n_{r}}(\mathfrak{h})$, when
$V_{\mathrm{fat}}(\mathfrak{h})=\\{f_{1},f_{2},\ldots,f_{r}\\}$ and
$n_{1}=n_{2}=\dots=n_{r}=n$. With the above notations, we can now state the
result of Hoffman and Ostrowski. For a proof of it, see [52, Theorem 2.14].

######  Theorem 3.9.

Suppose $\mathfrak{h}$ is a Hoffman graph with fat vertices
$f_{1},f_{2},\dots,f_{r}$.Then

$\lambda_{\min}(\mathfrak{g}^{n_{1},\dots,n_{r}}(\mathfrak{h}))\geq\lambda_{\min}(\mathfrak{h})$,

and

$\lim_{n_{1},\dots,n_{r}\rightarrow\infty}\lambda_{\min}(\mathfrak{g}^{n_{1},\dots,n_{r}}(\mathfrak{h}))=\lambda_{\min}(\mathfrak{h}).$

######  Definition 3.10 (representation of Hoffman graphs).

For a Hoffman graph $\mathfrak{h}$ and a positive integer $m$, a mapping
$\phi:V(\mathfrak{h})\to\mathbb{R}^{m}$ (resp.
$\phi:V(\mathfrak{h})\to\mathbb{Z}^{m}$) satisfying

$(\phi(x),\phi(y))=\left\\{\begin{array}[]{ll}t&\text{if }x=y\text{ and
}x,y\in V_{\mathrm{slim}}(\mathfrak{h});\\\ 1&\text{if }x=y\text{ and }x,y\in
V_{\mathrm{fat}}(\mathfrak{h});\\\ 1&\text{if }x\sim y;\\\
0&\text{otherwise},\end{array}\right.$

is a (resp. integral) representation of $\mathfrak{h}$ of norm $t$.

We denote by $\Lambda(\mathfrak{h},t)$ the lattice generated by the set
$\\{\phi(x)\mid x\in V(\mathfrak{h})\\}$. Note that the isomorphism class of
$\Lambda(\mathfrak{h},t)$ depends only on $\mathfrak{h}$ and $t$, and is
independent of $\phi$, justifying the notation.

######  Definition 3.11 (reduced representation of Hoffman graphs).

For a Hoffman graph $\mathfrak{h}$ and a positive integer $m$, a mapping
$\psi:V_{\mathrm{slim}}(\mathfrak{h})\to\mathbb{R}^{m}$ (resp.
$\phi:V(\mathfrak{h})\to\mathbb{Z}^{m}$) satisfying

$(\psi(x),\psi(y))=\left\\{\begin{array}[]{ll}t-|N_{\mathfrak{h}}^{f}(x)|&\text{if
}x=y;\\\ 1-|N_{\mathfrak{h}}^{f}(x,y)|&\text{if }x\sim y;\\\
-|N_{\mathfrak{h}}^{f}(x,y)|&\text{otherwise},\end{array}\right.$

is a (resp. integral) reduced representation of $\mathfrak{h}$ of norm $t$.

We denote by $\Lambda^{\text{red}}(\mathfrak{h},t)$ the lattice generated by
the set $\\{\psi(x)\mid x\in V_{\mathrm{slim}}(\mathfrak{h})\\}$. Note that
the isomorphism class of $\Lambda^{\text{red}}(\mathfrak{h},t)$ also depends
only on $\mathfrak{h}$ and $t$, and is independent of $\psi$, justifying the
notation.

######  Lemma 3.12 ([52, Theorem $2.8$]).

For a Hoffman graph $\mathfrak{h}$, the following conditions are equivalent:

  1. (i)

$\mathfrak{h}$ has a representation of norm $t$;

  2. (ii)

$\mathfrak{h}$ has a reduced representation of norm $t$;

  3. (iii)

$\lambda_{\min}(\mathfrak{h})\geq-t$.

A Hoffman graph $\mathfrak{h}$ is called _integrally representable of norm
$t$_, if $\mathfrak{h}$ has an integral representation
$\phi:V(\mathfrak{h})\rightarrow\mathbb{Z}^{m}$ of norm $t$ for some $m$.

###  3.1 Sum and decomposition

######  Definition 3.13 (sum).

Let $\mathfrak{h}^{1}$ and $\mathfrak{h}^{2}$ be two Hoffman graphs. A Hoffman
graph $\mathfrak{h}$ is the sum of $\mathfrak{h}^{1}$ and $\mathfrak{h}^{2}$,
denoted by $\mathfrak{h}=\mathfrak{h}^{1}\uplus\mathfrak{h}^{2}$, if
$\mathfrak{h}$ satisfies the following condition:

There exists a partition
$\big{\\{}V_{\mathrm{slim}}^{1}(\mathfrak{h}),V_{\mathrm{slim}}^{2}(\mathfrak{h})\big{\\}}$
of $V_{\mathrm{slim}}(\mathfrak{h})$ such that induced Hoffman subgraphs
generated by $V_{\mathrm{slim}}^{i}(\mathfrak{h})$ are $\mathfrak{h}^{i}$ for
$i=1,2$ and

$Sp(\mathfrak{h})=\begin{pmatrix}Sp(\mathfrak{h}^{1})&O\\\
O&Sp(\mathfrak{h}^{2})\end{pmatrix}$

with respect to the partition
$\big{\\{}V_{\mathrm{slim}}^{1}(\mathfrak{h}),V_{\mathrm{slim}}^{2}(\mathfrak{h})\big{\\}}$
of $V_{\mathrm{slim}}(\mathfrak{h})$.

Clearly, by definition, the sum is associative, so that the sum
$\biguplus_{i=1}^{r}\mathfrak{h}^{i}$ is well-defined. We can check that
$\mathfrak{h}$ is a sum of two non-empty Hoffman graphs if and only if
$Sp(\mathfrak{h})$ is a block matrix with at least two blocks. If
$\mathfrak{h}=\mathfrak{h}^{1}\uplus\mathfrak{h}^{2}$ for some non-empty
Hoffman subgraphs $\mathfrak{h}^{1}$ and $\mathfrak{h}^{2}$, then we call
$\mathfrak{h}$ _decomposable_ with $\\{\mathfrak{h}^{1},\mathfrak{h}^{2}\\}$
as a _decomposition_ and call $\mathfrak{h}^{1},\mathfrak{h}^{2}$ _factors_ of
$\mathfrak{h}$. Otherwise, $\mathfrak{h}$ is called _indecomposable_.

The following lemma gives a combinatorial way to define the sum of Hoffman
graphs.

######  Lemma 3.14 ([64, Lemma 2.11]).

Let $\mathfrak{h}$ be a Hoffman graph and $\mathfrak{h}^{1}$ and
$\mathfrak{h}^{2}$ be two induced Hoffman subgraphs of $\mathfrak{h}$. The
Hoffman graph $\mathfrak{h}$ is the sum of $\mathfrak{h}^{1}$ and
$\mathfrak{h}^{2}$ if and only if $\mathfrak{h}^{1}$, $\mathfrak{h}^{2}$, and
$\mathfrak{h}$ satisfy the following conditions:

  1. (i)

$V(\mathfrak{h})=V(\mathfrak{h}^{1})\cup V(\mathfrak{h}^{2});$

  2. (ii)

$\big{\\{}V_{\mathrm{slim}}(\mathfrak{h}^{1}),V_{\mathrm{slim}}(\mathfrak{h}^{2})\big{\\}}$
is a partition of $V_{\mathrm{slim}}(\mathfrak{h});$

  3. (iii)

if $x\in V_{\mathrm{slim}}(\mathfrak{h}^{i}),~{}f\in
V_{\mathrm{fat}}(\mathfrak{h})$ and $x\sim f$, then $f\in
V_{\mathrm{fat}}(\mathfrak{h}^{i});$

  4. (iv)

if $x\in V_{\mathrm{slim}}(\mathfrak{h}^{1})$ and $y\in
V_{\mathrm{slim}}(\mathfrak{h}^{2})$, then $x$ and $y$ have at most one common
fat neighbor, and they have one if and only if they are adjacent.

Let $\mu\leq-1$ be a real number and $\mathfrak{h}$ a Hoffman graph with
$\lambda_{\min}(\mathfrak{h})\geq\mu$. The Hoffman graph $\mathfrak{h}$ is
said to be _$\mu$ -reducible_ if there exists a Hoffman graph
$\widetilde{\mathfrak{h}}$ containing $\mathfrak{h}$ as an induced Hoffman
subgraph, such that there is a decomposition
$\\{\widetilde{\mathfrak{h}}_{i}\\}_{i=1}^{2}$ of $\widetilde{\mathfrak{h}}$
with $\lambda_{\min}(\widetilde{\mathfrak{h}}_{i})\geq\mu$ and
$V_{s}(\widetilde{\mathfrak{h}}_{i})\cap V_{s}(\mathfrak{h})\neq\emptyset\
(i=1,2)$. We say that $\mathfrak{h}$ is _$\mu$ -irreducible_ if
$\lambda_{\min}(\mathfrak{h})\geq\mu$ and $\mathfrak{h}$ is not
$\mu$-reducible. A Hoffman graph $\mathfrak{h}$ is said to be _reducible_ if
$\mathfrak{h}$ is $\lambda_{\min}(\mathfrak{h})$-reducible. We say
$\mathfrak{h}$ is _irreducible_ if $\mathfrak{h}$ is not reducible.

######  Definition 3.15 (line Hoffman graph).

Let $\mathfrak{H}$ be a family of pairwise non-isomorphic Hoffman graphs. A
Hoffman graph $\mathfrak{h}$ is an $\mathfrak{H}$-line Hoffman graph if there
exists a Hoffman graph $\mathfrak{h}^{\prime}$ satisfying the following
conditions:

  1. (i)

$\mathfrak{h}^{\prime}$ has $\mathfrak{h}$ as an induced Hoffman subgraph;

  2. (ii)

$\mathfrak{h}^{\prime}$ has the same slim graph as $\mathfrak{h}$;

  3. (iii)

$\mathfrak{h}^{\prime}=\biguplus_{i=1}^{r}\mathfrak{h}_{i}^{\prime}$, where
$\mathfrak{h}_{i}^{\prime}$ is isomorphic to an induced Hoffman subgraph of
some Hoffman graph in $\mathfrak{H}$ for $i=1,\dots,r$.

######  Definition 3.16 ($\mathfrak{H}$-saturated Hoffman graph).

Let $\mathfrak{H}$ be a family of pairwise non-isomorphic Hoffman graphs. A
Hoffman graph $\mathfrak{h}$ is $\mathfrak{H}$-saturated, if $\mathfrak{h}$ is
an $\mathfrak{H}$-line Hoffman graph, and no fat vertex can be attached to
$\mathfrak{h}$ in such a way that the resulting Hoffman graph is also an
$\mathfrak{H}$-line Hoffman graph.

Note that if we set $\mathfrak{H}$ to be the family of pairwise non-isomorphic
$\mu$-irreducible Hoffman graphs, then a $\mu$-saturated Hoffman graph is
$\mathfrak{H}$-saturated.

###  3.2 $\mathfrak{H}$-Saturated Hoffman graphs

Now we depict several Hoffman graphs as follows. They appeared in [94] for the
first time. Actually some of them are not used in this paper, but we use the
same symbols as in [94] to avoid confusion.

$\mathfrak{h}_{1}$ =$\mathfrak{h}_{2}$ =$\mathfrak{h}_{3}$ =
$\mathfrak{h}_{4}$ =$\mathfrak{h}_{5}$ =$\mathfrak{h}_{6}$ =
$\mathfrak{h}_{7}$ =$\mathfrak{h}_{8}$ =$\mathfrak{h}_{9}$ = Figure 1:

We first state a classical result by Krausz [65].

######  Theorem 3.17.

A graph $G$ of order $n$ is a line graph if and only if one can partition the
edge-set of $G$ into cliques $\\{C_{1},C_{2},\ldots,C_{t}\\}$ such that each
vertex lies in at most $2$ $C_{i}$’s. Moreover, if $G$ is a connected line
graph and $n\geq 7$, then this partition into cliques is unique.

In terms of line Hoffman graphs, we can formulate this result as follows.

######  Theorem 3.18.

Every $\\{\mathfrak{h}_{2}\\}$-line Hoffman graph whose slim graph is
connected of order at least $7$ has a unique
$\\{\mathfrak{h}_{2}\\}$-saturated Hoffman graph containing it, up to strong
isomorphism.

In [32], Cvetković, Doob and Simić showed a similar result for generalized
line graphs. We formulate their result in terms of line Hoffman graphs as
follows.

######  Theorem 3.19.

Every $\\{\mathfrak{h}_{2},\mathfrak{h}_{3}\\}$-line Hoffman graph whose slim
graph is connected of order at least $7$ has a unique
$\\{\mathfrak{h}_{2},\mathfrak{h}_{3}\\}$-saturated Hoffman graph containing
it, up to strong isomorphism.

Taniguchi [84] showed the following result, although in his paper he used
different terminology.

######  Theorem 3.20.

Every $\\{\mathfrak{h}_{2},\mathfrak{h}_{5}\\}$-line Hoffman graph whose slim
graph is connected of order at least $8$ has a unique
$\\{\mathfrak{h}_{2},\mathfrak{h}_{5}\\}$-saturated Hoffman graph containing
it, up to strong isomorphism.

In [37], Furuya, Kubota, Taniguchi and Yoshino generalized Theorem 3.20. In
[85], Taniguchi showed that if a graph is not the slim graph of a
$\\{\mathfrak{h}_{2},\mathfrak{h}_{5}\\}$-line Hoffman graph but each of its
proper induced subgraph is the slim graph of a
$\\{\mathfrak{h}_{2},\mathfrak{h}_{5}\\}$-line Hoffman graph, then this graph
is just isomorphic to one of $38$ graphs, found by computer. In [67], Kubota,
Taniguchi and Yoshino gave more related results.

###  3.3 Minimal fat Hoffman graphs

Let $\mu<0$ be a real number. A Hoffman graph $\mathfrak{h}$ is said to be
_$t$ -fat-minimal_ for $\mu$, if it is $t$-fat, its smallest eigenvalue is
less than $\mu$, and each of its proper $t$-fat induced Hoffman subgraph has
smallest eigenvalue at least $\mu$. For convenience, a $1$-fat-minimal Hoffman
graph for $\mu$ is also said to be _fat-minimal_ for $\mu$.

Woo and Neumaier [94] determined all the fat-minimal Hoffman graphs for
$-1-\sqrt{2}$. By checking their results, one can find that every fat-minimal
Hoffman graph for $-1-\sqrt{2}$ has at most $4$ slim vertices.

Later Koolen et al. [62] studied fat-minimal Hoffman graphs for $-3$. They
found that every fat-minimal Hoffman graph for $-3$ has at most $10$ slim
vertices. Moreover, if a fat-minimal Hoffman graph for $-3$ has a slim vertex
with at least $2$ fat neighbors, then it has at most $2$ slim vertices.

Here we introduce an important family of fat Hoffman graphs. Let $H$ be a
graph. Let $\mathfrak{q}(H)$ be the fat Hoffman graph with slim graph $H$ and
one fat vertex attached to all slim vertices. Then the special matrix of
$\mathfrak{q}(H)$ is $-I-A(\overline{H})$, where $\overline{H}$ is the
complement of $H$. Let $\lambda_{0}(\overline{H})$ be the largest eigenvalue
of $\overline{H}$. We have:

$\lambda_{\min}(\mathfrak{q}(H))=-1-\lambda_{0}(\overline{H})$ (4)

immediately. We will show that if $\mathfrak{q}(H)$ is fat-minimal for $\mu$,
then its smallest eigenvalue can not be much smaller than $\mu$. To prove it,
some preparation is necessary.

######  Lemma 3.21 ([81, Corollary 2.2]).

Let $G=(V(G),E(G))$ be a connected graph with the largest eigenvalue
$\lambda_{0}(G)$ and the principal eigenvector $\mathbf{v}$, the positive
eigenvector of norm $1$ with eigenvalue $\lambda_{0}(G)$. For each vertex $x$
of $G$, let $G-x$ be the subgraph of $G$ induced on $V(G)-\\{x\\}$ with the
largest eigenvalue $\lambda_{0}(G-x)$. Then

$\frac{1-2\mathbf{v}_{x}^{2}}{1-\mathbf{v}_{x}^{2}}\lambda_{0}(G)\leq\lambda_{0}(G-x)\leq\lambda_{0}(G),$
(5)

where $\mathbf{v}_{x}$ is the $x$-coordinate of the vector $\mathbf{v}$.

This lemma has the following consequence.

######  Proposition 3.22.

Let $\lambda$ be a positive real number and $G$ a graph of order $n\geq 3$
with the largest eigenvalue $\lambda_{0}(G)$. If $\lambda_{0}(G)>\lambda$ and
for every proper induced subgraph $H$ of $G$, the largest eigenvalue
$\lambda_{0}(H)$ of $H$ is at most $\lambda$, then
$\lambda_{0}(G)\leq\frac{n-1}{n-2}\lambda$.

######  Proof.

It is not hard to see that $G$ is connected. Let $\mathbf{v}$ be the principal
eigenvector of $G$. Take a vertex $x$ of $G$ such that $\mathbf{v}_{x}$ is
minimal. Then $\mathbf{v}_{x}\leq\frac{1}{\sqrt{n}}$ as the norm of
$\mathbf{x}$ is equal to $1$. Now apply Lemma 3.21 to this vertex $x$ and we
obtain the desired inequality. This completes the proof. ∎

######  Lemma 3.23.

Let $\mu<0$ be a real number and $n\geq 3$ a positive integer. Let
$\mathfrak{q}(H)$ be a Hoffman graph with $n$ slim vertices. If
$\mathfrak{q}(H)$ is fat-minimal for $\mu$, then
$\lambda_{\min}(\mathfrak{q}(H))\geq\mu+\frac{1+\mu}{n-2}$.

######  Proof.

As $\mathfrak{q}(H)$ is a fat-minimal Hoffman graph for $\mu$, we have
$\lambda_{\min}(\mathfrak{q}(H))<\mu$, and thus
$\lambda_{0}(\overline{H})>-1-\mu$ by (4). Assume $K:=\overline{H^{\prime}}$
is a proper induced subgraph of $\overline{H}$, where $H^{\prime}$ is a proper
induced subgraph of $H$. Considering the minimality of $\mathfrak{q}(H)$, we
have
$-1-\lambda_{0}(\overline{H^{\prime}})=\lambda_{\min}(\mathfrak{q}(H^{\prime}))\geq\mu$
by (4). This means
$\lambda_{0}(K)=\lambda_{0}(\overline{H^{\prime}})\leq-1-\mu$. Now the
conditions of Proposition 3.22 are satisfied, and we can easily obtain
$\lambda_{0}(\overline{H})\leq\frac{n-1}{n-2}(-1-\mu)$. By using (4) again, we
have
$\lambda_{\min}(\mathfrak{q}(H))=-1-\lambda_{0}(\overline{H})\geq\mu+\frac{1+\mu}{n-2}$.
∎

###  3.4 Maximal $\mu$-irreducible Hoffman graphs

A $\mu$-irreducible Hoffman graph is _maximal_ , if it is not a proper induced
Hoffman subgraph of another $\mu$-irreducible Hoffman graph. Notice that if a
$\mu$-irreducible Hoffman graph is maximal, then it is $\mu$-saturated and
indecomposable.

Woo and Neumaier [94] found that there are exactly $4$ maximal
$(-1-\sqrt{2})$-irreducible Hoffman graphs, up to isomorphism, and they are
$\mathfrak{h}_{2}$, $\mathfrak{h}_{5}$, $\mathfrak{h}_{7}$ and
$\mathfrak{h}_{9}$ in Figure 1.

Let $\tau$ be the golden ratio $\frac{1+\sqrt{5}}{2}$. In 2014, Munemasa, Sano
and Taniguchi [76] found that there are exactly $18$ maximal
$(-1-\tau)$-irreducible Hoffman graphs, up to isomorphism, and they also gave
a list of these $18$ Hoffman graphs.

As for the fat maximal $(-3)$-irreducible Hoffman graphs, we refer to [52] and
[58]. To state the main results there, we need to define the special graph of
a Hoffman graph. (Signed graphs and switching equivalence will be introduced
in Section 7.)

######  Definition 3.24 (special graph).

The special graph of a Hoffman graph $\mathfrak{h}$ is the signed graph

$\mathcal{S}(\mathfrak{h}):=(V(\mathcal{S}(\mathfrak{h})),E^{+}(\mathcal{S}(\mathfrak{h})),E^{-}(\mathcal{S}(\mathfrak{h}))),$

where $V(\mathcal{S}(\mathfrak{h}))=V_{\mathrm{slim}}(\mathfrak{h})$ and

$\displaystyle E^{+}(\mathcal{S}(\mathfrak{h}))=$
$\displaystyle\\{\\{x,y\\}\mid x,y\in V_{\mathrm{slim}}(\mathfrak{h}),x\neq
y,\\{x,y\\}\in E(\mathfrak{h}),N_{\mathfrak{h}}^{f}(x,y)=\emptyset\\},$
$\displaystyle E^{-}(\mathcal{S}(\mathfrak{h}))=$
$\displaystyle\\{\\{x,y\\}\mid x,y\in V_{\mathrm{slim}}(\mathfrak{h}),x\neq
y,\\{x,y\\}\in E(\mathfrak{h}),|N_{\mathfrak{h}}^{f}(x,y)|\geq 2\\}$
$\displaystyle\cup$ $\displaystyle\\{\\{x,y\\}\mid x,y\in
V_{\mathrm{slim}}(\mathfrak{h}),x\neq y,\\{x,y\\}\not\in
E(\mathfrak{h}),N_{\mathfrak{h}}^{f}(x,y)\neq\emptyset\\}.$

The _special $\varepsilon$-graph_ of $\mathfrak{h}$ is the graph
$S^{\epsilon}(\mathfrak{h})=(V_{\mathrm{slim}}(\mathfrak{h}),E^{\epsilon}(\mathcal{S}(\mathfrak{h})))$
for $\epsilon\in\\{+,-\\}$.

Let $\mathfrak{h}$ be a fat indecomposable Hoffman graph with
$\lambda_{\min}(\mathfrak{h})\geq-3$. It is shown in [52] that, if
$\mathfrak{h}$ is not the Hoffman graph  , then its special graph is connected
and the lattice $\Lambda^{\text{red}}(\mathfrak{h},3)$ is either an
irreducible root lattice or a sublattice of the standard lattice. Moreover, if
$\mathfrak{h}$ is a fat maximal $(-3)$-irreducible Hoffman graph and the
lattice $\Lambda^{\text{red}}(\mathfrak{h},3)$ is a sublattice of the standard
lattice, that is $\mathfrak{h}$ is fat maximal $(-3)$-irreducible with an
integral representation of norm $3$, then the graph $S^{-}(\mathfrak{h})$ is
connected and is (isomorphic to) the Dynkin diagrams $A_{n}$, $D_{n}$ or the
extended Dynkin diagram $\hat{A}_{n},\hat{D}_{n}$ for some positive integer
$n$ (see Figure 2). Using this result of [52], Koolen, Li and Yang [58]
classified the fat maximal $(-3)$-irreducible Hoffman graphs with an integral
representation of norm $3$. As for the fat maximal $(-3)$-irreducible Hoffman
graphs with no integral representation of norm $3$, the classification is
still open.

$A_{n}$$D_{n}$$\hat{A}_{n}$$\hat{D}_{n}$ Figure 2:

A related result was shown by Munemasa, Sano and Taniguchi [77] and Greaves,
Koolen, Munemasa, Sano and Taniguchi [45]. In [77], Munemasa et al. gave a
characterization of special graphs of fat Hoffman graphs with smallest
eigenvalue greater than $-3$ which contain a slim vertex having two fat
neighbors. In [45, Theorem 20], Greaves et al. showed that for a fat Hoffman
graph in which every slim vertex has exactly one fat neighbor, it has smallest
eigenvalue greater than $-3$ if and only if its special graph is switching
equivalent to certain signed graphs.

##  4 Graphs with large minimal valency

In this section, we give some results on graphs with fixed smallest eigenvalue
and large minimal valency. We start with the associated Hoffman graphs.

###  4.1 Associated Hoffman graphs

In this subsection, we summarize some facts about associated Hoffman graphs
and quasi-cliques, which provide some connections between Hoffman graphs and
graphs. For more details, we refer to [54] and [64].

Let $m$ be a positive integer and $G$ a graph that does not contain
$\widetilde{K}_{2m}$ as an induced subgraph, where $\widetilde{K}_{2m}$ is the
graph defined before Theorem 2.9. Let $\mathcal{C}(n)=\\{C\mid$ $C$ is a
maximal clique of $G$ of order at least $n\\}$. Define the relation
$\equiv_{n}^{m}$ on $\mathcal{C}(n)$ by $C_{1}\equiv_{n}^{m}C_{2}$ if each
vertex $x\in C_{1}$ has at most $m-1$ non-neighbors in $C_{2}$ and each vertex
$y\in C_{2}$ has at most $m-1$ non-neighbors in $C_{1}$. Note that
$\equiv_{n}^{m}$ is an equivalence relation if $n\geq(m+1)^{2}$.

Let $[C]_{n}^{m}$ denote the equivalence class of $\mathcal{C}(n)$ of $G$
under the equivalence relation $\equiv_{n}^{m}$ containing the maximal clique
$C$ of $\mathcal{C}(n)$. We define the _quasi-clique_ $Q([C]_{n}^{m})$ of $C$
with respect to the pair $(m,n)$ as the subgraph of $G$ induced on the set
$\\{x\in V(G)\mid$ $x$ has at most $m-1$ non-neighbors in $C\\}$. Note that
for any $C^{\prime}\in[C]_{n}^{m}$, we have
$Q([C^{\prime}]_{n}^{m})=Q([C]_{n}^{m})$ (see [54, Lemma 3.3]).

Let $[C_{1}]_{n}^{m},\dots,[C_{r}]_{n}^{m}$ be the equivalence classes of
maximal cliques under $\equiv_{n}^{m}$. The _associated Hoffman graph_
$\mathfrak{g}=\mathfrak{g}(G,m,n)$ is the Hoffman graph satisfying the
following conditions:

  1. (i)

$V_{\mathrm{slim}}(\mathfrak{g})=V(G)$,
$V_{\mathrm{fat}}(\mathfrak{g})=\\{f_{1},f_{2},\dots,f_{r}\\}$;

  2. (ii)

the slim graph of $\mathfrak{g}$ equals $G$;

  3. (iii)

for each $i$, the fat vertex $f_{i}$ is adjacent to exactly all the vertices
of $Q([C_{i}]_{n}^{m})$ for $i=1,2,\dots,r.$

From the above definition of associated Hoffman graphs, we find that for each
$i=1,\dots,r$, the quasi-clique $Q([C_{i}]_{n}^{m})$ of $C_{i}$ with respect
to the pair $(m,n)$ is exactly the quasi-clique $Q_{\mathfrak{g}}(f_{i})$ in
$\mathfrak{g}$ with respect to the fat vertex $f_{i}$.

The following result, which is a crucial tool for the study of graphs with
fixed smallest eigenvalue and large minimal valency, was shown in [54,
Proposition 4.1].

######  Proposition 4.1.

Let $G$ be a graph and let $m\geq 2,\phi,\sigma,p\geq 1$ be integers. There
exists a positive integer $n=n(m,\phi,\sigma,p)\geq(m+1)^{2}$ such that, for
any integer $q\geq n$ and any Hoffman graph $\mathfrak{h}$ with at most $\phi$
fat vertices and at most $\sigma$ slim vertices, the graph $G(\mathfrak{h},p)$
is an induced subgraph of $G$, provided that the graph $G$ satisfies the
following conditions:

  1. (i)

the graph $G$ does not contain $\widetilde{K}_{2m}$ as an induced subgraph,

  2. (ii)

its associated Hoffman graph $\mathfrak{g}=\mathfrak{g}(G,m,q)$ contains
$\mathfrak{h}$ as an induced Hoffman subgraph.

In order to use this proposition well, we need the following definition.

######  Definition 4.2 ($(r,\lambda)$-nice Hoffman graph).

Let $r$ be a positive integer and $\lambda\leq-1$ a real number. A Hoffman
graph $\mathfrak{h}$ is $(r,\lambda)$-nice, if it contains no induced Hoffman
subgraph with the number of slim vertices at most $r$ and smallest eigenvalue
less than $\lambda$.

######  Theorem 4.3.

Let $\lambda\leq-2$ be a real number and $r$ a positive integer. Let $m$ be
such that the smallest eigenvalue of $\widetilde{K}_{2m}$ is less than
$\lambda$. Then there exists a positive integer
$N=N(\lambda,m,r)\geq(m+1)^{2}$ such that, for any graph $G$ with smallest
eigenvalue at least $\lambda$, the associated Hoffman graph
$\mathfrak{g}=\mathfrak{g}(G,m,q)$ is $(r,\lambda)$-nice if $q\geq N$.

######  Proof.

Let $\mathfrak{h}^{(\lceil-\lambda\rceil+1)}$ be the Hoffman graph with one
slim vertex adjacent to $\lceil-\lambda\rceil+1$ fat vertices, and let

$\mathfrak{G}=\left\\{\mathfrak{h}^{(\lceil-\lambda\rceil+1)}\right\\}\cup\left\\{\mathfrak{h}\mid\lambda_{\min}(\mathfrak{h})<\lambda,|V_{\mathrm{slim}}(\mathfrak{h})|\leq
r,|N_{\mathfrak{h}}^{f}(x)|\leq\lceil-\lambda\rceil\text{ for all }x\in
V_{\mathrm{slim}}(\mathfrak{h})\right\\}$

be a family of pairwise non-isomorphic Hoffman graphs. It is not hard to see
that the family $\mathfrak{G}$ is finite and we may assume
$\mathfrak{G}=\\{\mathfrak{f}_{1},\mathfrak{f}_{2},\ldots,\mathfrak{f}_{s}\\}$.
As $\lambda_{\min}(\mathfrak{f}_{i})<\lambda$ for each $i=1,\ldots,s$, there
exist positive integers $p_{i}$’s such that
$\lambda_{\min}(G(\mathfrak{f}_{i},p_{i}))<\lambda$ hold by Theorem 3.9. Let
$p=\max_{1\leq i\leq s}p_{i}$, $\phi=\max_{1\leq i\leq
s}|V_{\mathrm{fat}}(\mathfrak{f}_{i})|$ and let $N$ be the positive integer
$n(m,\phi,r,p)$ such that Proposition 4.1 holds. Now for a given graph $G$
with $\lambda_{\min}(G)\geq\lambda$ and an integer $q>N$, we will show that
the associated Hoffman graph $\mathfrak{g}(G,m,q)$ is $(r,\lambda)$-nice.
Suppose not. Then $\mathfrak{g}(G,m,q)$ contains a Hoffman graph in
$\mathfrak{G}$ as an induced Hoffman subgraph. Without loss of generality, we
may assume $\mathfrak{f}_{1}$ is an induced Hoffman subgraph of
$\mathfrak{g}(G,m,q)$. Proposition 4.1 says that under this condition the
graph $G$ contains $G(\mathfrak{f}_{1},p)$ as an induced subgraph. Now we
obtain a contradiction, as $\lambda_{\min}(G(\mathfrak{f}_{1},p))<\lambda$ and
$\lambda_{\min}(G)\geq\lambda$. Hence the theorem holds. ∎

###  4.2 Graphs with large minimal valency

In this subsection, we focus on graphs with fixed smallest eigenvalue and
large minimal valency.

Let $G$ be a graph. For a given vertex $x$ of $G$, we call the subgraph of $G$
induced on the neighbors of $x$ the _local graph_ of $G$ at $x$, and denote it
by $\Delta_{G}(x)$. For convenience, we also denote by $k_{G}(x)$ the valency
of $x$ and $\bar{k}(\Delta_{G}(x))$ the average valency of the graph
$\Delta_{G}(x)$, that is,

$k_{G}(x)=|V(\Delta_{G}(x))|,\mathrm{and}\bar{k}(\Delta_{G}(x))=\frac{2|E(\Delta_{G}(x))|}{|V(\Delta_{G}(x))|}.$

Let $p$ be a positive integer. A $p$-_plex_ is an induced subgraph in which
each vertex is adjacent to all but at most $p$ of the vertices. Note that a
clique is exactly the same as a $1$-plex.

We define $\mathfrak{G}(t)$ to be the family of pairwise non-isomorphic
indecomposable $t$-fat Hoffman graphs with special matrix $(-t-1)$ or
$\begin{pmatrix}J_{s_{1}}-(t+1)I&-J\\\ -J&J_{s_{2}}-(t+1)I\end{pmatrix}$ where
$1\leq s_{1},s_{2}\leq t$.

Using associated Hoffman graphs the following five results have been shown.

######  Theorem 4.4 (cf. [64, Theorem 1.2]).

Let $t\geq 2$ be an integer. Then there exists a positive integer $C_{2}(t)$
such that, if a graph $G$ satisfies the following conditions:

  1. (i)

$k_{G}(x)>C_{2}(t)$ holds for all $x\in V(G),$

  2. (ii)

any $(t^{2}+1)$-plex containing $x$ has order at most
$\frac{k_{G}(x)-C_{2}(t)}{t}$ for all $x\in V(G),$

  3. (iii)

$\lambda_{\min}(G)\geq-t-1$,

then $G$ is the slim graph of a $t$-fat $\mathfrak{G}(t)$-line Hoffman graph.

######  Theorem 4.5 (cf. [64, Theorem 1.3]).

Let $t\geq 2$ be an integer. Then there exists a positive integer $C_{3}(t)$
such that, if a graph $G$ satisfies the following conditions:

  1. (i)

$k_{G}(x)>C_{3}(t)$ holds for all $x\in V(G),$

  2. (ii)

$\bar{k}(\Delta_{G}(x))\leq\frac{k_{G}(x)-C_{3}(t)}{t}$ holds for all $x\in
V(G)$,

  3. (iii)

$\lambda_{\min}(G)\geq-t-1$,

then $G$ is the slim graph of a $t$-fat $\mathfrak{G}(t)$-line Hoffman graph.

In the next two results, we focus on graphs with smallest eigenvalue at least
$-3$.

######  Theorem 4.6 ([64, Theorem 1.4]).

There exists a positive integer $\kappa_{2}$ such that, if a graph $G$
satisfies the following conditions:

  1. (i)

$k_{G}(x)>\kappa_{2}$ holds for all $x\in V(G),$

  2. (ii)

any $5$-plex containing $x$ has order at most $k_{G}(x)-\kappa_{2}$ for all
$x\in V(G),$

  3. (iii)

$\lambda_{\min}(G)\geq-3$,

then $G$ is the slim graph of a $2$-fat { ,  ,  }-line Hoffman graph.

######  Theorem 4.7 ([64, Theorem 1.5]).

There exists a positive integer $\kappa_{3}$ such that, if a graph $G$
satisfies the following conditions:

  1. (i)

$k_{G}(x)>\kappa_{3}$ holds for all $x\in V(G),$

  2. (ii)

$\bar{k}(\Delta_{G}(x))\leq k_{G}(x)-\kappa_{3}$ holds for all $x\in V(G)$,

  3. (iii)

$\lambda_{\min}(G)\geq-3$,

then $G$ is the slim graph of a $2$-fat { ,  ,  }-line Hoffman graph.

The following result is important in the proof of Theorem 2.2.

######  Theorem 4.8 ([62, Theorem 5.3]).

There exists a positive integer $\kappa_{4}$ such that, if $G$ is a graph with
smallest eigenvalue at least $-3$ and minimal valency at least $\kappa_{4}$,
then $G$ is the slim graph of a fat Hoffman graph with smallest eigenvalue at
least $-3$.

We now show how to obtain Theorem 2.2 from Theorem 4.8. Assume that $G$ is the
slim graph of the fat Hoffman graph $\mathfrak{h}$ with smallest eigenvalue at
least $-3$. Without loss of generality, we may assume
$-3\leq\lambda_{\min}(G)<-2$ by Theorem 2.1. Following from Lemma 3.12, we
find that $\mathfrak{h}$ has a reduced representation of norm $3$ and denote
it by $\psi$. Then for each vertex $x$ of $G$, we let
$N_{x}:=\psi(x)+\sum\limits_{f\sim x,f\in
V_{\mathrm{fat}}(\mathfrak{h})}\mathbf{e}_{f}$, where $\\{\mathbf{e}_{f}\mid
f\in V_{\mathrm{fat}}(\mathfrak{h})\\}$ is a set of orthonormal integral
vectors which are orthogonal to all of the vectors in the set $\\{\psi(y)\mid
y\in V(G)\\}$. It is not hard to check that the matrix $N$ with $N_{x}$’s as
its columns satisfies the equation $A(G)+3I=N^{T}N$. Thus

$\Lambda(G)=\langle N_{x}\mid x\in
V(G)\rangle_{\mathbb{Z}}=\langle\psi(x)+\sum_{\begin{subarray}{c}f\sim x,\\\
f\in V_{\mathrm{fat}}(\mathfrak{h})\end{subarray}}\mathbf{e}_{f}\mid x\in
V(G)\rangle_{\mathbb{Z}}.$

This implies that the integrability of the integral lattice $\Lambda(G)$
depends on the integrability of the integral lattice
$\Lambda^{\text{red}}(\mathfrak{h},3):=\langle\psi(x)\mid x\in
V(G)\rangle_{\mathbb{Z}}$. Note that for each $x$, the norm of the vector
$\psi(x)$ is at most $2$, as $\mathfrak{h}$ is fat. Hence the integral lattice
$\Lambda^{\text{red}}(\mathfrak{h},3)$ is the direct sum of $E_{i}$’s,
$D_{i}$’s, $A_{i}$’s and $\mathbb{Z}^{q}$ where $q$ is a non-negative integer.
As each of these lattices is $s$-integrable (see [31, Corollary 23]) for any
$s\geq 2$, Theorem 4.8 holds.

##  5 Distance-regular graphs

In this section, we give some results on distance-regular graphs that have
fixed smallest eigenvalue or whose local graphs have fixed smallest
eigenvalue. We start with some definitions.

###  5.1 Definitions

Let $G$ be a $k$-regular graph of order $n$. If every pair of adjacent
vertices of $G$ has exactly $a$ common neighbors, and every pair of distinct
and non-adjacent vertices of $G$ has exactly $c$ common neighbors, then $G$ is
called _strongly regular_ with parameters $(n,k,a,c)$.

Let $G$ be a connected graph with diameter $D$. For each vertex $x$ of $G$,
denote by $G_{i}(x)$ the set of vertices at distance precisely $i$ from $x$,
where $0\leq i\leq D$. For any two vertices $x$ and $y$, denote by $d(x,y)$
the distance between $x$ and $y$. The graph $G$ is called _distance-regular_
if there are positive integers

$b_{0},b_{1},\ldots,b_{D-1},c_{1}=1,c_{2},\ldots,c_{D}$

such that for any two vertices $x$ and $y$ with $d(x,y)=i$, $|G_{i-1}(x)\cap
G_{1}(y)|=c_{i}$ ($1\leq i\leq D$) and $|G_{i+1}(x)\cap G_{1}(y)|=b_{i}$
($0\leq i\leq D-1$). Set $b_{D}=c_{0}=0$. The numbers $b_{i},c_{i}$ and
$a_{i}:=b_{0}-b_{i}-c_{i}$ ($0\leq i\leq D$) are called the _intersection
numbers_ of $G$. The array
$\iota(G):=\\{b_{0},b_{1},\ldots,b_{D-1};c_{1},c_{2},\ldots,c_{D}\\}$ is
called the _intersection array_ of $G$. Note that a distance-regular graph of
diameter $2$ and order $n$ is a strongly regular graph with parameters
$(n,b_{0},a_{1},c_{2})$.

Let $G$ be a distance-regular graph with valency $k$ and smallest eigenvalue
$\lambda_{\min}(G)$. As observed by Godsil, the order of a clique $C$ in $G$
satisfies the Delsarte bound, that is,

$|V(C)|\leq 1+\frac{k}{-\lambda_{\min}(G)},$

and we say that $C$ is a _Delsarte clique_ if its order equals
$1+\frac{k}{-\lambda_{\min}(G)}$. We say that $G$ is _geometric_ if there
exists a family $\mathcal{F}$ of Delsarte cliques in $G$ such that each edge
of $G$ lies in exactly one of the Delsarte cliques of $\mathcal{F}$. Although
the family $\mathcal{F}$ of Delsarte cliques in geometric distance-regular
graphs is not always unique, usually it is.

###  5.2 Strongly regular graphs with fixed smallest eigenvalue

It is well-known that a connected strongly regular graph such that its
complement is disconnected is complete multipartite (see [43, Lemma 10.1.1]).
So in this subsection, we will deal with connected strongly regular graphs
whose complements are also connected, that is, the so-called _primitive_
strongly regular graphs.

We start this subsection with two important families of geometric primitive
strongly regular graphs.

Family 1: A _Steiner system_ $S(2,t,v)$ is a pair $(\mathcal{P},\mathcal{B})$,
where $\mathcal{P}$ is a $v$-element set called a _point set_ and
$\mathcal{B}$ is a family of $t$-element subsets of $\mathcal{P}$ called a
_block set_ such that each $2$-element subset of $\mathcal{P}$ is contained in
exactly one block. Take a Steiner system $S(2,t,v)$. Construct a graph as
follows: its vertex set is the block set of this Steiner system, and two
blocks are adjacent whenever they intersect in one point. This gives a
geometric strongly regular graph with parameters
$(\frac{v(v-1)}{t(t-1)},\frac{t(v-t)}{t-1},(t-1)^{2}+\frac{v-1}{t-1}-2,t^{2})$
(see [29, p. 5]). We call this graph the _block graph_ of the Steiner system
and call this family the _Steiner family_.

Family 2: An _orthogonal array_ with parameters $t$ and $v$ is a $t\times
v^{2}$ array with entries in $\\{1,2,\ldots,v\\}$ such that the $v^{2}$
ordered pairs in any two distinct rows are all different. We denote an
orthogonal array with these parameters by $OA(v,t)$. Note that an $OA(v,3)$ is
equivalent to a Latin square. Take an $OA(v,t)$ orthogonal array
$\mathcal{O}$. Construct a graph as follows: its vertex set is the set of
columns of $\mathcal{O}$, and two columns are adjacent whenever they have the
same entries in (exactly) one position. This gives a geometric strongly
regular graph with parameters $(v^{2},(v-1)t,v-2+(t-1)(t-2),t(t-1))$ (see [43,
Theorem 10.4.2]). We call this family the _Latin square family_.

Neumaier [79] showed the following theorem for strongly regular graphs with
fixed smallest eigenvalue.

######  Theorem 5.1 (cf. [79, Theorem 4.7]).

Let $G$ be a primitive strongly regular graph with parameters $(n,k,a,c)$ and
smallest eigenvalue $-\lambda$, where $\lambda\geq 2$ is an integer. If
$(\lambda+1)(a+1)-k>(c-1)\binom{\lambda+1}{2}$, then one of the following
holds:

  1. (i)

$G$ is in the Latin square family with parameters
$((s+1)^{2},s\lambda,s-1+(\lambda-1)(\lambda-2),\lambda(\lambda-1))$, where
$s$ is a positive integer;

  2. (ii)

$G$ is in the Steiner family with parameters
$(n,s\lambda,s-1+(\lambda-1)^{2},\lambda^{2})$, where $s$ is a positive
integer and $n=(s+1)(s(\lambda-1)+\lambda)/\lambda$.

He showed this theorem in two steps. The first step was to show the following
result.

######  Theorem 5.2 (cf.[79, Theorem 4.6]).

Let $G$ be a primitive strongly regular graph with parameters $(n,k,a,c)$ and
smallest eigenvalue $-\lambda$, where $\lambda\geq 2$ is an integer. If
$(\lambda+1)(a+1)-k>(c-1)\binom{\lambda+1}{2}$, then $G$ is geometric.

As step two, he determined the geometric strongly regular graphs with
parameters $(n,k,a,c)$ and smallest eigenvalue $-\lambda$, where $\lambda\geq
2$ is an integer, such that $(\lambda+1)(a+1)-k>(c-1)\binom{\lambda+1}{2}$.

A non-complete connected regular graph is strongly regular if and only if it
has exactly $3$ distinct eigenvalues (see [43, Lemma 10.2.1]). Now we discuss
some results on connected non-regular graphs with $3$ distinct eigenvalues.

In [90], Van Dam determined the connected non-regular graphs with $3$ distinct
eigenvalues with smallest eigenvalue at least $-2$.

In [18], Cheng, Greaves and Koolen determined the connected non-regular graphs
with $3$ distinct eigenvalues with second largest eigenvalue at most $1$.

Motivated by Neumaier’s theorem, that is Theorem 5.1, Cheng, Gavrilyuk,
Greaves, and Koolen [17] showed that for any $\lambda\geq 2$, there exists a
constant $n_{1}(\lambda)$ such that any connected non-bipartite biregular
graph, with exactly $3$ distinct eigenvalues
$\lambda_{0}>\lambda_{1}>\lambda_{2}$ satisfying $\lambda_{1}\leq\lambda$, has
at most $n_{1}(\lambda)$ vertices. In the same paper, Cheng et al. asked
whether the conclusion holds if the condition $\lambda_{1}\leq\lambda$ is
replaced by $\lambda_{2}\geq-\lambda$. Cheng and Koolen [19] answered this
question in the affirmative. This latter paper used the ideas of Hoffman,
without actually introducing Hoffman graphs.

###  5.3 Distance-regular graphs with fixed smallest eigenvalue

There are four important families of geometric distance-regular graphs: the
Hamming graphs, the Johnson graphs, the Grassmann graphs and the bilinear
forms graphs. One of the reasons that they are important is that for fixed
diameter there are infinitely many graphs in each of these four families.

Let $D\geq 1$ and $q\geq 2$ be integers. Let $X$ be a finite set of size $q$.
The _Hamming graph_ $H(D,q)$ is the graph with the vertex set
$X^{D}:=\prod_{i=1}^{D}X$ (the Cartesian product of $D$ copies of $X$), where
two vertices are adjacent whenever they differ in precisely one coordinate. In
particular, if $D=2$, then a Hamming graph $H(2,q)$ is the line graph of a
complete bipartite graph $K_{q,q}$. We also call a Hamming graph $H(2,q)$ a _(
$q\times q$)-grid_.

Let $v,D$ be integers. Let $X$ be a finite set of size $v$. The _Johnson
graph_ $J(v,D)$ is the graph with vertex set $\binom{X}{D}$, the set of all
$D$-element subsets of $X$, where two vertices are adjacent whenever they
intersect in precisely $D-1$ elements. In particular, if $D=2$, then a Johnson
graph $J(v,2)$ is the line graph of a complete graph $K_{v}$. We also call a
Johnson graph $J(v,2)$ a _triangular graph_ and denote it by $T(v)$. (Since
the Johnson graph $J(v,D)$ is isomorphic to the Johnson graph $J(v,v-D)$, we
always assume $v\geq 2D$.)

Let $v,D$ be integers such that $v\geq D$ and $q$ a prime power. Let
$\mathbb{F}$ be a finite field of order $q$ and $V$ a $v$-dimensional vector
space over $\mathbb{F}$. The _Grassmann graph_ $J_{q}(v,D)$ is the graph with
the set of all $D$-dimensional subspaces of $V$ as the vertex set, where two
vertices are adjacent whenever their intersection is a $(D-1)$-dimensional
subspace of $V$. (Since the Grassmann graph $J_{q}(v,D)$ is isomorphic to the
Grassmann graph $J_{q}(v,v-D)$, we will also always assume $v\geq 2D$.)

Let $D,e$ be integers such that $e\geq D$ and $q$ a prime power. Let
$\mathbb{F}$ be a finite field of order $q$. The _bilinear forms graph_
$Bil(D\times e,q)$ is the graph with the set of all $D\times e$ matrices over
$\mathbb{F}$ as the vertex set, where two vertices are adjacent whenever the
rank of their difference equals one.

Koolen and Bang [55] generalized Theorem 5.2 to the class of distance-regular
graphs under the extra condition that $c_{2}\geq 2$, by showing:

######  Theorem 5.3 (cf. [55, Theorem 1.3]).

For given $\lambda\geq 2$, there are only finitely many non-geometric
distance-regular graphs with both valency and diameter at least $3$,
$c_{2}\geq 2$ and smallest eigenvalue at least $-\lambda$.

Now we are going to show that in Theorem 5.3, the condition $c_{2}\geq 2$ can
be removed. Suppose that $G$ is distance-regular with $c_{2}=1$. It is not
hard to see that $G$ has no induced $K_{2,1,1}$’s, and thus $G$ is locally the
disjoint union of $(a_{1}+1)$-cliques, that is, the local graph of $G$ at each
vertex is the disjoint union of $(a_{1}+1)$-cliques (see [6, Propositon
1.2.1]). We say that a distance-regular graph is of _order_ $(s,t)$, if it is
locally the disjoint union of $t+1$ $K_{s}$’s. The next lemma gives a
sufficient condition for a distance-regular graph of order $(s,t)$ to be
geometric.

######  Lemma 5.4 (cf. [82, Proposition 3.1.6],[93, Corollary 7.7]).

Let $G$ be a distance-regular graph of order $(s,t)$ with diameter $D\geq 2$.
If $s>t$, then $G$ is geometric.

Lemma 5.4 implies that for a non-geometric distance-regular graph of order
$(s,t)$ with smallest eigenvalue at least $-\lambda$, its valency $k$
satisfies $k=s(t+1)\leq t(t+1)\leq(\lambda^{2}-1)\lambda^{2}$, as it contains
a $(t+1)$-claw $K_{1,t+1}$ with smallest eigenvalue $-\sqrt{t+1}$ as an
induced subgraph, which implies $-\sqrt{t+1}\geq-\lambda$ by Lemma 3.7. Now
using the fact that the Bannai-Ito conjecture, that is, for fixed $k\geq 3$
there are only finitely many distance-regular graphs with valency $k$, is true
(see [7, Theorem 1.1]), we find that there are only finitely many non-
geometric distance-regular graphs with both valency and diameter at least $3$,
$c_{2}=1$ and smallest eigenvalue at least $-\lambda$. Hence we obtain:

######  Theorem 5.5.

For given $\lambda\geq 2$, there are only finitely many non-geometric
distance-regular graphs with both valency and diameter at least $3$ and
smallest eigenvalue at least $-\lambda$.

######  Remark 5.6.

  1. (i)

Note that the (general) result was known for $\lambda=2$, see [12, Theorem
3.12.4, Theorem 4.2.16].

  2. (ii)

Godsil [44] gave a special case for this result for antipodal distance-regular
graphs of diameter $3$.

Koolen and Bang [55] gave the following two conjectures for geometric
distance-regular graphs.

######  Conjecture 5.7 ([55, Conjecture 7.4]).

For a fixed integer $\lambda\geq 2$, any geometric distance-regular graph with
smallest eigenvalue $-\lambda$, diameter $D\geq 3$ and $c_{2}\geq 2$ either is
a Hamming graph, a Johnson graph, a Grassmann graph, a bilinear forms graph,
or has the number of vertices bounded above by a function of $\lambda$.

######  Conjecture 5.8 ([55, Conjecture 7.5]).

For a fixed integer $\lambda\geq 2$, the diameter of a geometric distance-
regular graph with smallest eigenvalue $-\lambda$ and valency at least $3$ is
bounded above by a function of $\lambda$.

Note that Conjecture 5.7 can be seen as a generalization of Theorem 5.1 for
the class of distance-regular graphs. Now we discuss recent progress on
Conjecture 5.8. Bang [6] showed the following result:

######  Proposition 5.9 (cf. [6, Theorem 1.1]).

Fix an integer $\lambda\geq 2$. Suppose that $G$ is a geometric distance-
regular graph with diameter $D\geq 2$ and smallest eigenvalue $-\lambda$. If
$G$ contains an induced subgraph $K_{2,1,1}$, then $D\leq\lambda$.

For a distance-regular graph $G$ with intersection array
$\\{b_{0},b_{1},\ldots,b_{D-1};c_{1},c_{2},\ldots,c_{D}\\}$, define the head
$h:=h(G)=|\\{i\mid(c_{i},a_{i},b_{i})=(c_{1},a_{1},b_{1})\\}|$. The following
is known for geometric distance-regular graphs with order $(s,t)$ and is due
to Suzuki [82].

######  Proposition 5.10 (cf. [82, Proposition 3.1.6],[93, Corollary 7.7]).

Let $G$ be a distance-regular graph of order $(s,t)$ with head $h$ and
diameter $D\geq 2$. If $s>t$, then $D\leq t(h+1)+1$.

Note that the smallest eigenvalue of a geometric distance-regular graph of
order $(s,t)$ is equal to $-t-1$. Combining Propositions 5.9 and 5.10, we
obtain:

######  Corollary 5.11.

Let $\lambda\geq 2$ be an integer and $G$ a geometric distance-regular graph
with head $h$, diameter $D\geq 2$ and smallest eigenvalue $-\lambda$. Then
$D\leq(\lambda-1)(h+1)+1$.

This means that in order to solve Conjecture 5.8, we only need to show that
the head of a geometric distance-regular graph with smallest eigenvalue
$-\lambda$ is bounded above by a function of $\lambda$.

###  5.4 Characterizations of distance-regular graphs

Note that Bannai’s problem asks to classify the $Q$-polynomial distance-
regular graphs with large diameter. (See Appendix A for the definition of a
$Q$-polynomial distance-regular graph.) One part of this problem is to
characterize the known infinite families as a distance-regular graph. We say
that a distance-regular graph has _classical parameters_ $(D,b,\alpha,\beta)$,
if its diameter is $D$ and its intersection array is given as follows:

$\displaystyle b_{i}=$
$\displaystyle(\genfrac{[}{]}{0.0pt}{}{D}{1}-\genfrac{[}{]}{0.0pt}{}{i}{1})(\beta-\alpha\genfrac{[}{]}{0.0pt}{}{i}{1}),$
$\displaystyle c_{i}=$
$\displaystyle\genfrac{[}{]}{0.0pt}{}{i}{1}(1+\alpha\genfrac{[}{]}{0.0pt}{}{i-1}{1})$

($i=0,1,\ldots,D$), where

$\genfrac{[}{]}{0.0pt}{}{i}{j}=\left\\{\begin{array}[]{ll}\prod\limits_{\ell=0}^{j-1}\frac{i-\ell}{j-\ell}&\text{
if }b=1,\\\
\prod\limits_{\ell=0}^{j-1}\frac{b^{i}-b^{\ell}}{b^{j}-b^{\ell}}&\text{ if
}b\neq 1.\end{array}\right.$

An important subproblem of Bannai’s problem is to classify the distance-
regular graphs with classical parameters $(D,b,\alpha,\beta)$, as every
distance-regular graph with classical parameters is $Q$-polynomial (see [12,
Corollary 8.4.1]). Note that all the known infinite families of distance-
regular graphs with unbounded diameter are either classical or closely related
to classical distance-regular graphs. If a distance-regular graph $G$ has
classical parameters $(D,b,\alpha,\beta)$ where $D\geq 3$, then $b$ is an
integer equals neither $0$ nor $-1$ and if $b$ is positive, then the second
largest eigenvalue $\lambda_{1}$ of $G$ satisfies
$\lambda_{1}=\frac{b_{1}}{b}-1$ (see [12, Proposition 6.2.1] and [12,
Corollary 8.4.2]). In Lemma 6.2 we will relate the smallest eigenvalue of any
local graph of a distance-regular graph with $\frac{b_{1}}{\lambda_{1}+1}$,
where $\lambda_{1}$ is the second largest eigenvalue of this distance-regular
graph. For the rest of this subsection, we discuss the characterization of
distance-regular graphs with second largest eigenvalue $\lambda_{1}=b_{1}-1$,
the Grassmann graphs and the bilinear forms graphs. For more details and also
for more characterizations, see [40] and [93, Section 9]. For more information
on the known families of distance-regular graphs with unbounded diameter, see
[12, Chapter 9].

Characterization of distance-regular graphs with second largest eigenvalue
$\lambda_{1}=b_{1}-1$

It is known that, if a distance-regular graph contains an induced quadrangle,
then the second largest eigenvalue $\lambda_{1}$ is at most $b_{1}-1$ (see
[12, Proposition 4.4.9]). Distance-regular graphs that have second largest
eigenvalue $b_{1}-1$ include the Hamming graphs and the Johnson graphs. In the
next result we characterize the distance-regular graphs with second largest
eigenvalue $\lambda_{1}=b_{1}-1$. This result is due to Terwilliger and
Neumaier, independently.

######  Theorem 5.12 (cf. [12, Thoerem 4.4.11]).

Let $G$ be a distance-regular graph with second largest eigenvalue
$\lambda_{1}=b_{1}-1$. Then at least one of the following holds:

  1. (i)

$G$ is a strongly regular graphs with smallest eigenvalue $-2$;

  2. (ii)

$c_{2}=1$;

  3. (iii)

$c_{2}=2$ and $G$ is a Hamming graph $H(D,q)$, a Doob graph (see [12, p.
262]), the Conway-Smith graph with intersection array
$\\{10,6,4,1;1,2,6,10\\}$ (see [12, p. 399]) or the Doro graph with
intersection array $\\{10,6,4;1,2,5\\}$ (see [12, Chapter 12.1]);

  4. (iv)

$c_{2}=4$ and $G$ is a Johnson graph $J(v,D)$ where $v\geq 2D$;

  5. (v)

$c_{2}=6$ and $G$ is a halved cube (see [12, p. 264]);

  6. (vi)

$c_{2}=10$ and $G$ is the Gosset graph with intersection array
$\\{27,10,1;1,10,27\\}$ (see [12, p. 103]).

Note that this theorem also classifies the distance-regular graphs with
classical parameters $(D,1,\alpha,\beta)$ (see [12, Theorem 6.1.1]).

As corollaries we have the following characterizations of the Hamming graphs
and the Johnson graphs. The characterization of the Hamming graphs is due to
Egawa and the characterization of the Johnson graphs is due to Terwilliger.

######  Theorem 5.13 (cf. [12, Corollary 9.2.5]).

Let $G$ be a distance-regular graph with the same intersection array as a
Hamming graph $H(D,q)$. Then $G$ is the Hamming graph $H(D,q)$ or, if $q=4$, a
Doob graph.

######  Theorem 5.14 (cf. [86, Corollary 1.2]).

Let $G$ be a distance-regular graph with the same intersection array as a
Johnson graph $J(v,D)$, where $v\geq 2D$. Then $G$ is the Johnson graph
$J(v,D)$, or if $(v,D)=(8,2)$, a Chang graph.

Characterization of the Grassmann graphs

Metsch [73], building on work of many people, characterized the Grassmann
graphs as follows.

######  Theorem 5.15 ([73, Corollary 1.2]).

Let $G$ be a distance-regular graph with the same intersection array as a
Grassmann graph $J_{q}(v,D)$, where $v\geq 2D\geq 6$ are integers and $q\geq
2$ is a prime power. Then $G$ is the Grassmann graph $J_{q}(v,D)$ if
$v\geq\max\\{2D+2,2D+6-q\\}$.

His approach is to find large cliques, called grand cliques and show that each
edge lies in such a unique grand clique.

Gavrilyuk and Koolen [38] characterized the Grassmann graph $J_{q}(2D,D)$ as
follows.

######  Theorem 5.16.

Let $G$ be a distance-regular graph with the same intersection array as a
Grassmann graph $J_{q}(2D,D)$, where $D\geq 3$ is an integer and $q\geq 2$ is
a prime power. Then $G$ is the Grassmann graph $J_{q}(2D,D)$ if $D\geq 9$.

They first showed that the local graph of such a graph must have the same
spectrum as the $q$-clique extension of the
$(\frac{q^{D}-1}{q-1}\times\frac{q^{D}-1}{q-1})$-grid. Furthermore, using the
$Q$-polynomial property they showed that the local graph at any vertex
satisfies that every pair of distinct non-adjacent vertices has the same
number of common neighbors (we call graphs with this property co-edge regular
graphs and study them in the next section). Then following from Theorem 6.7,
they had that the local graph is really the $q$-clique extension of the
$(\frac{q^{D}-1}{q-1}\times\frac{q^{D}-1}{q-1})$-grid, if $D\geq 9$. Now
building on work of Numata, Cooperstein and Cohen (see [12, Theorem 9.3.8]),
they completed their proof.

Note that the situation for distance-regular graphs with the same parameters
as a Grassmann graph $J_{q}(2D+1,D)$ is very different, as Van Dam and Koolen
[92] constructed a distance-regular graph $\tilde{J}_{q}(2D+1,D)$ with the
same parameters as $J_{q}(2D+1,D)$, where $q$ is a prime power and $D\geq 2$
is an integer. For these graphs, not every edge lies in a maximum clique. This
shows that the method used by Metsch can not work in this case. Whether there
is a geometric argument for this case is not clear on this moment. Note that
Munemasa and Tonchev [78] showed that the block graph of the design
constructed by Jungnickel and Tonchev [53] is (isomorphic to) the graph
$\tilde{J}_{q}(2D+1,D)$.

Characterization of the bilinear forms graphs.

Metsch [74], again building on work of many people, characterized the bilinear
forms graphs as follows.

######  Theorem 5.17 ([74, Corollary 1.2]).

Let $G$ be a distance-regular graph with the same intersection array as a
bilinear forms graph $Bil(D\times e,q)$, where $e\geq D\geq 3$ are integers
and $q\geq 2$ is a prime power. If $q=2$ and $e\geq D+4$ or $q\geq 3$ and
$e\geq D+3$, then $G$ is the bilinear forms graph $Bil(D\times e,q)$.

His approach is the same as for the Grassmann graphs.

Gavrilyuk and Koolen [39] characterized the bilinear forms graph $Bil(D\times
D,2)$ as follows.

######  Theorem 5.18 ([39, Theorem 1.3]).

Let $G$ be a distance-regular graph with the same intersection array as a
bilinear forms graph $Bil(D\times D,2)$, where $D\geq 3$ is an integer. Then
$G$ is the bilinear forms graph $Bil(D\times D,2)$.

They first showed that the local graph of such a graph must be a
$((2^{D}-1)\times(2^{D}-1))$-grid by showing that the local graph must have
the same spectrum as the $((2^{D}-1)\times(2^{D}-1))$-grid. Then they used the
cliques of order $2^{D}$ to construct a geometry and using this geometry they
were able to show that the graph must be the bilinear forms graph $Bil(D\times
D,2)$.

###  5.5 Graphs cospectral to a distance-regular graph

In this subsection, we give some results on graphs cospectral to a distance-
regular graph.

We start with the Hamming graphs. Bang, Van Dam and Koolen [9] showed the
following results.

######  Proposition 5.19 ([9, Theorem 3.4]).

Let $q$ and $D\geq 2$ be positive integers. Let $2q>D^{4}+2D^{3}+2D^{2}-5D-4$.
Then any graph that is cospectral to $H(D,q)$ is locally the disjoint union of
$D$ cliques of order $q-1$.

They employed this result to show:

######  Proposition 5.20 ([9, Theorem 4.5]).

Let $q\geq 36$. Then the Hamming graph $H(3,q)$ is determined by its spectrum.

Using Theorem 4.5, Koolen Yang and Yang showed the following weaker result.

######  Theorem 5.21 (cf. [64, Theorem 1.6]).

There exists a positive integer $q^{\prime}$ such that for each $q\geq
q^{\prime}$, any graph that is cospectral to the Hamming graph $H(3,q)$ is the
slim graph of a $3$-fat { }-line Hoffman graph.

Next, we discuss the Johnson graphs. Again using Theorem 4.5, Koolen et al.
showed the following result.

######  Theorem 5.22 (cf. [64, Theorem 1.7]).

There exists a positive integer $v^{\prime}$ such that for each $v\geq
v^{\prime}$, any graph that is cospectral to the Johnson graph $J(v,3)$ is the
slim graph of a $3$-fat { }-line Hoffman graph.

Van Dam, Haemers, Koolen and Spence [91, p. 1814] gave a construction of
cospectral graphs of the Johnson graph $J(v,D)$ $(v\geq 2D\geq 4)$ that are
the block graphs of certain designs.

Similar results can be obtained for cospectral graphs of the Grassmann graphs
and the bilinear forms graphs.

##  6 Co-edge regular graphs

In this section, we discuss co-edge regular graphs with fixed smallest
eigenvalue. A $k$-regular graph of order $n$ is called _co-edge regular_ with
parameters $(n,k,c)$, if every pair of distinct and non-adjacent vertices has
exactly $c$ common neighbors. Note that a $(t_{1}\times t_{2})$-grid, which is
the line graph of a complete bipartite graph $K_{t_{1},t_{2}}$, is a co-edge
regular graph with parameters $(t_{1}t_{2},t_{1}+t_{2}-2,2)$.

The results in this section are motivated by two results of Terwilliger for
distance-regular graphs. The first result concerns the local graph of a thin
$Q$-polynomial distance-regular graph. For the definition of a thin
$Q$-polynomial distance-regular graph, see Appendix A.

######  Lemma 6.1 (cf. [88, Theorem 77]).

Let $G$ be a thin $Q$-polynomial distance-regular graph with diameter $D\geq
5$. Then there exists a non-negative integer $c$ such that for each vertex $x$
of $G$, the local graph $\Delta_{G}(x)$ at $x$ is co-edge regular with
parameters $(k,a_{1},c)$. Moreover, the local graph $\Delta_{G}(x)$ at $x$ has
at most $5$ distinct eigenvalues.

The second result shows a relation between the second largest eigenvalue of a
distance-regular graph and the smallest eigenvalue of its local graph at any
vertex.

######  Lemma 6.2 (cf. [12, Theorem 4.4.3]).

Let $G$ be a distance-regular graph with diameter $D\geq 3$ and second largest
eigenvalue $\lambda_{1}$. Then for each vertex $x$ of $G$, the local graph
$\Delta_{G}(x)$ at $x$ has the smallest eigenvalue at least
$-\frac{b_{1}}{\lambda_{1}+1}-1$.

Now we present an important tool shown by Yang and Koolen [95], by using
Hoffman graphs.

######  Proposition 6.3 ([95, Proposition 1.3]).

Let $\lambda\geq 2$ be a real number. Then there exists a constant
$M_{1}(\lambda)\geq\lambda^{3}$ such that, if a graph $G$ satifies

  1. (i)

every pair of vertices at distance $2$ has at least $M_{1}(\lambda)$ common
neighbors, and

  2. (ii)

$\lambda_{\min}(G)\geq-\lambda$,

then $G$ has diameter $2$ and for each $x$, the number of vertices at distance
$2$ to $x$ is at most $\lfloor\lambda\rfloor\lfloor(\lambda-1)^{2}\rfloor$.

Next we give an upper bound on the parameter $c$ for co-edge regular graphs in
terms of its smallest eigenvalue, due to Yang and Koolen [95]. They showed the
following:

######  Theorem 6.4 ([95, Theorem 7.1]).

Let $\lambda\geq 2$ be a real number. There exists a real number
$M_{2}(\lambda)$ such that, for any connected co-edge regular graph $G$ with
parameters $(n,k,c)$, if $\lambda_{\min}(G)\geq-\lambda$, then
$c>M_{2}(\lambda)$ implies that $n-k-1\leq\frac{(\lambda-1)^{2}}{4}+1$ holds.

Their proof used Proposition 6.3 and the Alon-Boppana Theorem. Later Koolen,
Gebremichel and Yang [57] observed that this result is also true when the
condition co-edge regular is replaced by sesqui-regular, which we are going to
introduce. A $k$-regular graph of order $n$ is called _sesqui-regular_ with
parameters $(n,k,c)$, if every pair of vertices at distance $2$ has exactly
$c$ common neighbors.

They further extended this result as follows:

######  Theorem 6.5.

Let $\lambda\geq 2$ be an integer. There exists a constant $C_{4}(\lambda)$
such that, for any sesqui-regular graph $G$ with parameters $(n,k,c)$, if
$\lambda_{\min}(G)\geq-\lambda$ and $k\geq C_{4}(\lambda)$, then one of the
following holds:

  * (i)

$c\leq\lambda^{2}(\lambda-1)$,

  * (ii)

$n-k-1\leq\frac{(\lambda-1)^{2}}{4}+1$.

######  Remark 6.6.

  1. (i)

The block graph of a Steiner system $S(2,t,v)$ is strongly regular with
parameters
$(\frac{v(v-1)}{t(t-1)},\frac{t(v-t)}{t-1},(t-1)^{2}+\frac{v-1}{t-1}-2,t^{2})$
and smallest eigenvalue $-t$. This shows that the bound in the first item of
the above theorem can not be improved too much.

  2. (ii)

There exists an infinite family of bipartite Ramanujan graphs with valency $k$
and unbounded number of vertices, which were found by Marcus et al. [71], as
we already discussed in Section 1.1. Let $G$ be a graph in this family, say of
order $n$. Consider the complement $\overline{G}$ of $G$. Then the following
holds:

    1. (a)

$\overline{G}$ has valency $n-k-1$;

    2. (b)

$\overline{G}$ has smallest eigenvalue at least $-1-2\sqrt{k-1}$ as $G$ has
second largest eigenvalue at most $2\sqrt{k-1}$.

This shows that the bound in the second item of Theorem 6.5 is tight.

  3. (iii)

In [56], it is shown that for $\lambda=3$, one can improve the bound in the
first item of the above theorem to $\lambda^{2}$. Whether this is true for
general $\lambda$, it is not known.

Now we give some spectral characterizations of some families of graphs under
the extra assumption that the graphs are co-edge regular. Hayat, Koolen and
Riaz [47] showed the following result for the clique-extensions of the square
grid graphs.

######  Theorem 6.7 ([47, Theorem 1.1]).

Let $G$ be a co-edge regular graph with spectrum

$\left\\{\big{(}s(2t+1)-1\big{)}^{1},(st-1)^{2t},(-1)^{(s-1)(t+1)^{2}},(-s-1)^{t^{2}}\right\\},$

where $s\geq 2,t\geq 1$ are integers. If $t\geq 11(s+1)^{3}(s+2)$, then $G$ is
the $s$-clique extension of the $((t+1)\times(t+1))$-grid.

Tan, Koolen and Xia [83] showed a similar result for the clique-extensions of
triangular graphs:

######  Theorem 6.8 ([83, Theorem 1]).

Let $G$ be a co-edge regular graph with spectrum

$\left\\{(2sv-3s-1)^{1},(sv-3s-1)^{v-1},(-s-1)^{\frac{v^{2}-3v}{2}},(-1)^{\frac{(s-1)v(v-1)}{2}}\right\\},$

where $s\geq 2$ and $v\geq 1$ are integers. If $v\geq 48s$, then $G$ is the
$s$-clique extension of the triangular graph $T(v)$.

######  Remark 6.9.

  1. (i)

Note that to prove both Theorems 6.7 and 6.8, they used the claw-clique method
of Bose and Laskar.

  2. (ii)

Using the method in [83], one could improve the bound $t\geq 11(s+1)^{3}(s+2)$
of Theorem 6.7.

Tan et al. [83] also gave the following conjecture:

######  Conjecture 6.10 ([83, Conjecture 3]).

Let $G$ be a connected co-edge regular graph with parameters $(n,k,c)$ having
four distinct eigenvalues. Let $\lambda\geq 2$ be an integer. Then there
exists a constant $n_{2}(\lambda)$ such that, if
$\lambda_{\min}(G)\geq-\lambda$, $n\geq n_{2}(\lambda)$ and
$k<n-2-\frac{(\lambda-1)^{2}}{4}$, then either $G$ is the $s$-clique extension
of a strongly regular graph for $2\leq s\leq\lambda-1$ or $G$ is a $(p\times
q)$-grid with $p>q\geq 2$.

Yang, Abiad and Koolen [96] showed the following spectral characterization of
$2$-clique extensions of the square grid graphs, using Hoffman graphs. They
did not need the assumption of co-edge regularity, but they needed a very
large lower bound on the valency.

######  Theorem 6.11 ([96, Theorem 1]).

The $2$-clique extension of the $(t\times t)$-grid is characterized by its
spectrum if $t$ is large enough.

In their proof, they used the following result of Koolen et al. [64].

######  Theorem 6.12 ([64, Theorem 1.8]).

There exists a positive integer $t$ such that for each pair $(t_{1},t_{2})$
with $t_{1}\geq t_{2}\geq t$, any graph that is cospectral to the $2$-clique
extension of the $(t_{1}\times t_{2})$-grid is the slim graph of a $2$-fat { ,
,  }-line Hoffman graph.

##  7 Signed graphs

###  7.1 Definitions

######  Definition 7.1 (signed graph).

A signed graph $(G,\tau)$ is a pair of a graph $G=(V(G),E(G))$ and a signing
$\tau:E(G)\rightarrow\\{+1,-1\\}$.

The _adjacency matrix_ $A(G,\tau)$ of the signed graph $(G,\tau)$ is the
symmetric matrix whose rows and columns are indexed by $V(G)$ such that
$A(G,\tau)_{x,y}=\tau(\\{x,y\\})$ if $\\{x,y\\}$ is an edge of $G$ and $0$
otherwise.

A real number $\lambda$ is an _eigenvalue_ of $(G,\tau)$, if $\lambda$ is an
eigenvalue of its adjacency matrix $A(G,\tau)$. The _spectrum_ of $(G,\tau)$
is the spectrum of $A(G,\tau)$. In a similar fashion, we denote by
$\lambda_{\min}(G,\tau)$ the smallest eigenvalue of the signed graph
$(G,\tau)$.

For $\varepsilon\in\\{+,-\\}$, the _$\varepsilon$ -graph_ of $(G,\tau)$ is the
graph $(G,\tau)^{\varepsilon}$ with vertex set $V(G)$ and edge set
$E^{\varepsilon}$, where $E^{\varepsilon}=\\{e\in E(G)\mid\tau(e)=\varepsilon
1\\}$. We also represent the signed graph $(G,\tau)$ by the triple
$(V(G),E^{+},E^{-})$.

Two signed graphs $(G,\tau)$ and $(H,\xi)$ are _switching equivalent_ if there
exist a permutation matrix $P$ and a diagonal matrix $D$ with diagonal entries
in $\\{-1,+1\\}$ such that $PA(G,\tau)P^{T}=DA(H,\xi)D$ holds.

###  7.2 Seidel matrices

In this subsection, we introduce and study Seidel matrices.

######  Definition 7.2 (Seidel matrix).

  1. (i)

A Seidel matrix $S$ of order $n$ is a symmetric $(0,\pm 1)$-matrix with $0$ on
the diagonal and $\pm 1$ otherwise.

  2. (ii)

Let $G$ be a graph. The Seidel matrix $S(G)$ of $G$ is the matrix $J-I-2A(G)$,
where $A(G)$ is the adjacency matrix of $G$.

Note that the Seidel matrix $S(G)$ of a graph $G$ of order $n$ is the
adjacency matrix of the signed graph $(K_{n},\tau_{G})$ satisfying
$(K_{n},\tau_{G})^{-}=G$. Therefore, for a given graph $G$ of order $n$, we
denote by $(K_{n},\tau_{G})$ the signed graph with $S(G)$ as its adjacency
matrix. Two graphs $G$ and $H$ of order $n$ are called _switching equivalent_
if the signed graphs $(K_{n},\tau_{G})$ and $(K_{n},\tau_{H})$ are switching
equivalent. If the graphs $G$ and $H$ are switching equivalent, then there
exists a subset $V^{\prime}$ of the vertex set $V(G)$ of $G$, such that the
resulting graph, by changing all the edges between $V^{\prime}$ and
$V(G)-V^{\prime}$ to non-edges, and all the non-edges between $V^{\prime}$ and
$V(G)-V^{\prime}$ to edges, is $H$. This operation is called _switching_ on
the subset $V^{\prime}$.

Note that switching equivalence is an equivalence relation. The equivalence
class of $G$ is called the _switching class_ of $G$ and is denoted by $[G]$.
If $H\in[G]$, the matrices $S(H)$ and $S(G)$ are similar and hence have the
same spectrum.

The motivation to study Seidel matrix with fixed smallest eigenvalue with
large multiplicity comes from the study of equiangular lines in the Euclidean
space.

######  Definition 7.3 (equiangular lines).

A system of lines through the origin in the $r$-dimensional Euclidean space
$\mathbb{R}^{r}$ is called equiangular if the angle between any pair of lines
is the same.

Seidel matrices and systems of equiangular lines, are related as follows (see
for example, [43, Section 11.1]):

######  Proposition 7.4.

Let $n>r\geq 2$ be integers. There exists a system of $n$ equiangular lines in
$\mathbb{R}^{r}$ with common angle $\arccos\alpha$ if and only if there exists
a Seidel matrix $S$ of order $n$ such that $S$ has smallest eigenvalue at
least $-\frac{1}{\alpha}$ and rank$(S+\frac{1}{\alpha}I)\leq r$.

We are going to use the theory of Hoffman graphs to study Seidel matrices with
fixed smallest eigenvalue. Our approach is different from, but closely related
to the approach of Balla, Dräxler, Keevash and Sudakov [5, Section 2].

Let $S$ be a Seidel matrix of order $n$. The graph $G^{+}(S)$ is the graph
with adjacency matrix $\frac{1}{2}(S+J-I)$. If $\lambda_{\min}(S)=2\lambda+1$,
then $\lambda_{\min}(G^{+}(S))\geq\lambda$. Note that for each graph in
$[G^{+}(S)]$, its smallest eigenvalue is at least $\lambda$. Let $C$ be a
clique of order $q$ in $H\in[G^{+}(S)]$. If necessary, by switching, we can
obtain a graph in $[G^{+}(S)]$ such that $C$ is still a clique and every
vertex outside $C$ has at least $q/2$ neighbors in $C$. We denote such a graph
by $H_{C}$.

######  Theorem 7.5.

Let $\lambda\leq-2$ be a real number and $r$ a positive integer. Let $m$ be
such that the smallest eigenvalue of $\widetilde{K}_{2m}$ is less than
$\lambda$. Then there exists a positive integer
$Q=Q(\lambda,m,r)\geq(m+1)^{2}$ such that for each integer $q\geq Q$ and each
Seidel matrix $S$ with $\lambda_{\min}(S)\geq 2\lambda+1$, if a graph
$H\in[G^{+}(S)]$ contains a clique $C$ of order at least $q$, then the
associated Hoffman graph $\mathfrak{g}=\mathfrak{g}(H_{C},m,q)$ is
$(r,\lambda)$-nice and has exactly one fat vertex and this fat vertex is
adjacent to all slim vertices.

Moreover there exists a positive integer $n=n(\lambda,q)$ such that if the
order of the Seidel matrix $S$ is at least $n$, then every graph in
$[G^{+}(S)]$ contains a clique of order at least $q$.

######  Proof.

Let $Q:=Q(\lambda,m,r)$ be the integer such that Theorem 4.3 holds. Let $q\geq
Q$. Suppose a graph $H\in[G^{+}(S)]$ has a clique $C$ of order at least $q$.
Without loss of generality, we may assume $C$ is a maximal clique in $H$. Now
we look at a graph $H_{C}$. It is known that all vertices outside $C$ have at
least $q/2$ neighbors in $C$. We claim that every vertex outside $C$ has at
most $m-1$ non-neighbors in $C$. Suppose this is not the case, and the vertex
$x$ outside $C$ has at least $m$ non-neighbors in $C$. Then we can find $m$
vertices $y_{1},y_{2},\ldots,y_{m}$ in $C$ which are not adjacent to $x$.
Since $x$ also has at least $q/2$ neighbors in $C$, where
$q/2\geq(m+1)^{2}/2\geq m$, we can find $z_{1},z_{2},\ldots,z_{m}$ in $C$
which are adjacent to $x$. It is not hard to see that the subgraph of $H_{C}$
induced on $\\{x,y_{1},y_{2},\ldots,y_{m},z_{1},z_{2},\ldots,z_{m}\\}$ is
$\widetilde{K}_{2m}$, which has smallest eigenvalue less than $\lambda$. This
is not possible, as $\lambda_{\min}(H_{C})\geq\lambda$. Hence, the claim
holds, and under the equivalence relation $\equiv_{q}^{m}$, the set of maximal
cliques in $H_{C}$ of order at least $q$ has exactly one equivalence class,
which consists of all vertices of $H_{C}$. This means that the associated
Hoffman graph $\mathfrak{g}(H_{C},m,q)$ has exactly one fat vertex and this
fat vertex is adjacent to all the slim vertices of $\mathfrak{g}(H_{C},m,q)$.
Considering $q\geq Q(\lambda,m,r)$, we have that $\mathfrak{g}(H_{C},m,q)$ is
$(r,\lambda)$-nice by Theorem 4.3.

Let $n:=R(q,\lceil-2\lambda\rceil+1)$, where $R(q,\lceil-2\lambda\rceil+1)$ is
the Ramsey number. For a graph $H^{\prime}\in[G^{+}(S)]$ with Seidel matrix
$S(H^{\prime})$, we claim that $H^{\prime}$ does not contain a stable set of
size $\lceil-2\lambda\rceil+1$. Otherwise, the matrix $S(H^{\prime})$ contains
a $((\lceil-2\lambda\rceil+1)\times(\lceil-2\lambda\rceil+1))$ principal
submatrix $J_{\lceil-2\lambda\rceil+1}-I_{\lceil-2\lambda\rceil+1}$. In other
words, the matrix $-S(H^{\prime})$ contains a principal submatrix
$-J_{\lceil-2\lambda\rceil+1}+I_{\lceil-2\lambda\rceil+1}$. Note that the
matrix $-S(H^{\prime})$ has the same spectrum as $S$. Thus

$\lceil
2\lambda\rceil=\lambda_{\min}(-J_{\lceil-2\lambda\rceil+1}+I_{\lceil-2\lambda\rceil+1})\geq\lambda_{\min}(-S(H^{\prime}))\geq
2\lambda+1,$

which gives a contradiction. (For the first inequality, see [42, Theorem
9.1.1].) Therefore, our claim holds and by Ramsey theory, the graph
$H^{\prime}$ contains a clique of order $q$.

This completes the proof. ∎

###  7.3 Signed graphs

Following a straightforward way, the notion of the $s$-integrability of graphs
can be extended to signed graph. For a positive integer $s$, we say that a
signed graph $(G,\tau)$ with smallest eigenvalue $\lambda_{\min}(G,\tau)$ is
_$s$ -integrable_, if there exists an integral matrix $N$ such that the
equality

$s(A(G,\tau)+\lceil-\lambda_{\min}(G,\tau)\rceil I)=N^{T}N$

holds, where $A(G,\tau)$ is the adjacency matrix of $(G,\tau)$.

Not so much is known about signed graphs with fixed smallest eigenvalue. Using
the same proof as in Theorem 2.1 one can show:

######  Theorem 7.6 ([10, Theorem 3.13]).

If $(G,\tau)$ is a connected signed graph with $\lambda_{\min}(G,\tau)\geq-2$,
then $(G,\tau)$ is $s$-integrable for $s\geq 2$. Moreover, if $(G,\tau)$ has
at least $121$ vertices, then $(G,\tau)$ is $1$-integrable.

Theorem 2.4 (i) has been extended to the class of signed graphs by Gavrilyuk,
Munemasa, Sano and Taniguchi [41] as follows.

######  Theorem 7.7.

For any real number $\lambda\in(-2,-1]$, there exists a constant
$C_{5}(\lambda)$ such that if $(G,\tau)$ is a connected signed graph on $n$
vertices with $\lambda_{\min}(G,\tau)\geq\lambda$ and minimal valency at least
$C_{5}(\lambda)$, then $\lambda_{\min}(G,\tau)=-1$ and $(G,\tau)$ is switching
equivalent to $(K_{n},+)$, and hence is $1$-integrable.

##  8 Future work

At the end of this survey, we give some problems for discussion.

###  8.1 Problems on graphs and signed graphs

First we discuss unsigned graphs. As a generalization of Theorem 2.2, we have

######  Problem 8.1 ([63, Conjecture 3.2]).

There exist constants $\kappa_{5}$ and $s_{1}$ such that, for any graph $G$
with $\lambda_{\min}(G)\geq-4$ and minimal valency at least $\kappa_{5}$, $G$
is $s_{1}$-integrable.

To solve this problem, we have to have a good understanding of fat Hoffman
graphs with smallest eigenvalue at least $-4$. The first step is to look at
the family $\mathfrak{H}$ of indecomposable fat Hoffman graphs with smallest
eigenvalue at least $-4$, in which every slim vertex has exactly one fat
neighbor and any two distinct slim vertices have no common fat neighbor. Note
that for any Hoffman graph in $\mathfrak{H}$, its slim graph is a connected
graph with smallest eigenvalue at least $-3$. Therefore, as a subproblem of
Problem 8.1, we have

######  Problem 8.2 ([63, Conjecture 3.1]).

There exists a constant $s_{2}$ such that, for any graph $G$ with
$\lambda_{\min}(G)\geq-3$, $G$ is $s_{2}$-integrable.

In [61], Koolen et al. showed that the complement of the McLaughlin graph has
smallest eigenvalue $-3$ and can not be $2$-integrated, but it is
$4$-integrable. It is not clear whether any graph with smallest eigenvalue at
least $-3$ is always $4$-integrable. The situation for graphs with smallest
eigenvalue at least $-3$ is different from the situation for graphs with
smallest eigenvalue at least $-2$, as there exists an infinite family of
connected graphs with unbounded vertices such that none of them can be
$2$-integrated (see [62, Remark 1.4 (v)]).

As a special case, we look at the integrability of trees with smallest
eigenvalue at least $-3$.

######  Problem 8.3.

Is it true that any tree with smallest eigenvalue at least $-3$ is
$2$-integrable?

In [60], Koolen, Rehman and Yang characterized $1$-integrable trees with
smallest eigenvalue at least $-3$.

For signed graphs we propose the following problems.

######  Problem 8.4.

For any real number $\lambda\in(-1-\sqrt{2},-2]$, there exists a constant
$C_{6}(\lambda)$ such that, if $(G,\tau)$ is a signed graph with
$\lambda_{\min}(G,\tau)\geq\lambda$ and minimal valency at least
$C_{6}(\lambda)$, then $\lambda_{\min}(G,\tau)=-2$ and $(G,\tau)$ is
$1$-integrable.

######  Problem 8.5.

There exists a constant $\kappa_{6}$ such that, if $(G,\tau)$ is a signed
graph with $\lambda_{\min}(G,\tau)\geq-3$ and minimal valency at least
$\kappa_{6}$, then $(G,\tau)$ is $s$-integrable for any $s\geq 2$.

To solve above two problems, one problem to overcome is how to deal with
switching classes of signed graphs. Is there a natural generalization of
Hoffman graphs to the class of signed graphs? In [41], they considered a
generalization of line Hoffman graphs. For more problems on graphs and signed
graphs with fixed smallest eigenvalue, see [63]. For more general problems on
the spectral theory of signed graphs, see [10].

###  8.2 Refining $\widetilde{K}_{2t}$

Denote by $H(a,t)$ the graph on $a+t+1$ vertices consisting of a clique
$K_{a+t}$ together with a vertex that is adjacent to precisely $a$ vertices of
this clique. Note that $\widetilde{K}_{2t}$ is exactly the graph $H(t,t)$.

In [46], Greaves, Koolen, and Park showed the following.

######  Lemma 8.6.

Let $G$ be a graph having smallest eigenvalue $-m$ that contains $H(a,t)$ as
an induced subgraph. Then

$(a-m(m-1))(t-(m-1)^{2})\leqslant(m(m-1))^{2}.$ (6)

Using the above result, they obtain bounds on the clique order in strongly
regular graphs. Their result can also be extended to other classes of graphs,
for example, distance-regular graphs.

Lemmens and Seidel [68] conjectured that for each Seidel matrix $S$ of order
$n$, the rank of the matrix $S+5I$ is at least $\lfloor\frac{2n}{3}\rfloor+1$.
This was shown to be true by Cao, Koolen, Lin and Yu [16]. Their main tool is
to use the Seidel matrices of the complements of $H(a,t)$’s as minimal
forbidden principal submatrices.

## Acknowledgments

J.H. Koolen is partially supported by the National Natural Science Foundation
of China (No. 12071454) and Anhui Initiative in Quantum Information
Technologies (No. AHY150000).

Q. Yang is partially supported by the Fellowship of China Postdoctoral Science
Foundation (No. 2020M671855).

We greatly thank Prof. Min Xu for supporting M.-Y. Cao to visit University of
Science and Technology of China.

We are also grateful to Prof. Sebastian M. Cioabă, Prof. Akihiro Munemasa, Dr.
Jongyook Park and Mr. Kiyoto Yoshino for their careful reading and valuable
comments.

##  Appendix A $Q$-polynomial distance-regular graphs

Let $V$ denote a non-empty finite set. Let $\mathrm{Mat}_{V}(\mathbb{C})$
denote the $\mathbb{C}$-algebra consisting of all complex matrices whose rows
and columns are indexed by $V$. Let $\mathds{U}=\mathbb{C}^{V}$ denote the
$\mathbb{C}$-vector space consisting of all complex vectors indexed by $V$. We
endow $\mathds{U}$ with standard Hermitian inner product
$(\mathbf{u},\mathbf{v})=\mathbf{u}^{T}\overline{\mathbf{v}}$ for
$\mathbf{u},\mathbf{v}\in\mathds{U}$. We view $\mathds{U}$ as a left module
for $\mathrm{Mat}_{V}(\mathbb{C})$, called the _standard module_.

Let $G$ be a distance-regular graph of diameter $D$. Let $V$ be the vertex set
of $G$. For $0\leq i\leq D$, let $A_{i}$ denote the matrix in
$\mathrm{Max}_{V}(\mathbb{C})$ defined by

$(A_{i})_{x,y}=\left\\{\begin{array}[]{ll}1&\text{ if }d(x,y)=i,\\\ 0&\text{
otherwise},\end{array}\right.$

where $x,y\in V$. We call $A_{i}$ the _ $i$th distance matrix_ of $G$. We
abbreviate $A:=A_{1}$. Observe that

  * (1a)

$A_{0}=I$;

  * (1b)

$\sum^{D}_{i=0}A_{i}=J$, the all-ones matrix;

  * (1c)

each $A_{i}$ is real symmetric;

  * (1d)

there exist $p_{ij}^{h}$ for $0\leq i,j,h\leq D$, such that
$A_{i}A_{j}=A_{j}A_{i}=\sum^{D}_{h=0}p^{h}_{ij}A_{h}$ hold.

Notice that (1a) implies for each pair vertices $x,y\in V$ with $d(x,y)=h$,
the equality $|G_{i}(x)\cap G_{j}(y)|=p_{ij}^{h}$ holds. Therefore, for all
integers $0\leq h,i,j\leq D$, $p^{h}_{ij}=0$ (resp. $p^{h}_{ij}\neq 0$) if one
of $h,i,j$ is greater than (resp. equal to) the sum of the other two. By these
facts, we find that $A_{0},A_{1},\ldots,A_{D}$ is a basis for a commutative
subalgebra $M$ of $\mathrm{Mat}_{V}(\mathbb{C})$, which we call the _Bose-
Mesner algebra_ of $G$. It is known that $A$ generates $M$, as
$AA_{i}=c_{i+1}A_{i+1}+a_{i}A_{i}+b_{i-1}A_{i-1}$ ($0\leq i\leq D$) by
condition (iv), where
$\\{b_{0},b_{1},\ldots,b_{D-1};c_{1},c_{2},\ldots,c_{D}\\}$ is the
intersection array of $G$.

The algebra $M$ has a second basis $E_{0},E_{1},\ldots,E_{D}$ such that

  * (2a)

$E_{0}=|V|^{-1}J$,

  * (2b)

$\sum^{D}_{i=0}E_{i}=I$,

  * (2c)

each $E_{i}$ is real symmetric,

  * (2d)

$E_{i}E_{j}=E_{j}E_{i}=\delta_{ij}E_{i}$

(see [12, p. 45]). We call $E_{i}$ the _$i$ th primitive idempotent_ of $G$.
Since $\\{E_{i}\\}^{D}_{i=0}$ is a basis for $M$, there exist complex scalars
$\\{\theta_{i}\\}^{D}_{i=0}$ such that $A=\sum^{D}_{i=0}\theta_{i}E_{i}$.
(Note that $\\{\theta_{i}\\}^{D}_{i=0}$ are exactly all of the distinct
eigenvalues of $G$ and they are real.) Observe $AE_{i}=E_{i}A=\theta_{i}E_{i}$
for $0\leq i\leq D$. We call $\theta_{i}$ the eigenvalue of $G$ associated
with $E_{i}$ for $0\leq i\leq D$. Observe $\mathds{U}=E_{0}\mathds{U}\oplus
E_{1}\mathds{U}\oplus\cdots\oplus E_{D}\mathds{U}$, an orthogonal direct sum.
For $0\leq i\leq D$, $E_{i}\mathds{U}$ is the eigenspace of $A$ associated
with $\theta_{i}$. Denote by $m_{i}$ the rank of $E_{i}$ and observe
$m_{i}=\dim(E_{i}\mathds{U})$, the multiplicity of the eigenvalue
$\theta_{i}$.

We now introduce the notion of $Q$-polynomial property of $G$. Let $\circ$
denote the entrywise product in $\mathrm{Mat}_{V}(\mathbb{C})$. Since
$A_{i}\circ A_{j}=\delta_{ij}A_{i}$, the Bose-Mesner algebra $M$ is closed
under $\circ$. Also as $\\{E_{i}\\}^{D}_{i=0}$ is a basis for $M$, there exist
complex scalars $q^{h}_{ij}$ such that

$E_{i}\circ E_{j}=|V|^{-1}\sum^{D}_{h=0}q^{h}_{ij}E_{h}.$

By [12, p. 48, p. 49], the scalars $q^{h}_{ij}$ are real and non-negative. We
say $G$ is _$Q$ -polynomial_ (with respect to the given ordering
$E_{0},E_{1},\ldots,E_{D}$) whenever for all integers $0\leq h,i,j\leq D$,
$q^{h}_{ij}=0$ (resp. $q^{h}_{ij}\neq 0$) if one of $h,i,j$ is greater than
(resp. equal to) the sum of the other two [12, p. 235].

We assume $G$ is $Q$-polynomial with respect to the ordering
$E_{0},E_{1},\ldots,E_{D}$. Fix a vertex $x\in V$. We refer to $x$ as a “base”
vertex. For $0\leq i\leq D$, we define the diagonal matrix
$E^{*}_{i}=E^{*}_{i}(x)\in\mathrm{Mat}_{V}(\mathbb{C})$ with diagonal entry

$(E^{*}_{i})_{y,y}=\left\\{\begin{array}[]{ll}1&\text{ if }d(x,y)=i,\\\
0&\text{ otherwise},\end{array}\right.$

where $y\in V$. We call $E^{*}_{i}$ the _$i$ th dual primitive idempotent_ of
$G$ with respect to $x$. Observe

  * (3a)

$\sum^{D}_{i=0}E^{*}_{i}=I$,

  * (3b)

each $E^{*}_{i}$ is real symmetric,

  * (3c)

$E^{*}_{i}E^{*}_{j}=\delta_{ij}E^{*}_{i}$.

By these facts, $E^{*}_{0},E^{*}_{1},\ldots,E^{*}_{D}$ is a basis for a
commutative subalgebra $M^{*}$ of $\mathrm{Mat}_{V}(\mathbb{C})$, which we
call the _dual Bose-Mesner algebra_ of $G$.

Define the diagonal matrix
$A^{*}_{i}=A^{*}_{i}(x)\in\mathrm{Mat}_{V}(\mathbb{C})$ with diagonal entry
$(A^{*}_{i})_{y,y}=|V|(E_{i})_{x,y}$ for $y\in V$. By [87, p. 379],
$A^{*}_{0},A^{*}_{1},\ldots,A^{*}_{D}$ is also a basis for $M^{*}$, and
moreover

  * (4a)

$A^{*}_{0}=I$,

  * (4b)

$\sum^{D}_{i=0}A^{*}_{i}=|V|E_{0}^{*}$,

  * (4c)

each $A_{i}^{*}$ is real and symmetric,

  * (4d)

$A^{*}_{i}A^{*}_{j}=A^{*}_{j}A^{*}_{i}=\sum^{D}_{h=0}q^{h}_{ij}A^{*}_{h}$.

We call $A^{*}_{i}$ the $i$th _dual distance matrix_ of $G$ with respect to
$x$. We abbreviate $A^{*}=A^{*}_{1}$, called the _dual adjacency matrix_ of
$G$ with respect to $x$. From conditions (4a) and (4d), we find that the
matrix $A^{*}$ generates $M^{*}$. Since $\\{E^{*}_{i}\\}^{D}_{i=0}$ is a basis
for $M^{*}$, there exist complex scalars $\\{\theta^{*}_{i}\\}^{D}_{i=0}$ such
that $A^{*}=\sum^{D}_{i=0}\theta^{*}_{i}E^{*}_{i}$. Observe
$A^{*}E^{*}_{i}=E^{*}_{i}A^{*}=\theta^{*}_{i}E^{*}_{i}$ for $0\leq i\leq D$.
The scalars $\\{\theta^{*}_{i}\\}^{D}_{i=0}$ are real [87, Lemma 3.11] and
mutually distinct. We call $\theta^{*}_{i}$ the _dual eigenvalue_ of $G$
associated with $E^{*}_{i}$. Observe $\mathds{U}=E^{*}_{0}\mathds{U}\oplus
E^{*}_{1}\mathds{U}\oplus\cdots\oplus E^{*}_{D}\mathds{U}$, an orthogonal
direct sum. For $0\leq i\leq D$, the space $E^{*}_{i}\mathds{U}$ is the
eigenspace of $A^{*}$ associated with $\theta^{*}_{i}$.

Let $T=T(x)$ denote the subalgebra of $\mathrm{Mat}_{V}(\mathbb{C})$ generated
by $M$ and $M^{*}$. We call $T$ the _Terwilliger algebra_ (or _subconstituent
algebra_) of $G$ with respect to $x$ [87]. Note that $A$ and $A^{*}(x)$
generates $T$. The algebra $T$ is finite dimensional and non-commutative. It
is also semi-simple since it is closed under conjugate and transpose map. The
following are relations in $T$ [87, Lemma 3.2]. For $0\leq h,i,j\leq D$,

$\displaystyle E^{*}_{i}A_{h}E^{*}_{j}=0\quad\text{if and only if}\quad
p^{h}_{ij}=0,$ $\displaystyle E_{i}A^{*}_{h}E_{j}=0\quad\text{if and only
if}\quad q^{h}_{ij}=0.$

Note that $T$ may depend on the choice of the base vertex (see [8]).

By a _$T$ -module_, we mean a subspace $\mathds{W}$ of $\mathds{U}$ such that
$B\mathds{W}\subseteq\mathds{W}$ for all $B\in T$. Observe that $\mathds{U}$
is a $T$-module, called the _standard module of $T$_ (or _standard
$T$-module_). A $T$-module is called _irreducible_ if it contains no
$T$-submodule except itself and zero module.

Let $\mathds{W}$ be a $T$-module and $\mathds{W}_{1}$ a $T$-submodule of
$\mathds{W}$. Then the orthogonal complement of $W_{1}$ in $W$ is a
$T$-module, since $T$ is closed under conjugate transpose map. It follows that
$W$ decomposes into an orthogonal direct sum of irreducible $T$-modules.

Let $W$ denote an irreducible $T$-module. Then $W$ decomposes into a direct
sum of nonzero spaces among $E^{*}_{i}W$, $0\leq i\leq D$. By the _endpoint_
of $W$, we mean $\min\\{i\mid 0\leq i\leq D,E^{*}_{i}W\neq 0\\}$. By the
_diameter_ of $W$, we mean $|\\{i\mid 0\leq i\leq D,E^{*}_{i}W\neq 0\\}|-1$.
Let $r$ denote the endpoint of $W$ and $d$ the diameter of $W$. By [87, Lemma
3.9], we have (i) $E^{*}_{i}W\neq 0$ if and only if $r\leq i\leq r+d$; (ii)
$W=\bigoplus^{d}_{h=0}E^{*}_{r+h}W$, an orthogonal direct sum. An irreducible
$T$-module $W$ is said to be _thin_ whenever $\dim(E^{*}_{i}W)\leq 1$ for
$0\leq i\leq D$. There exists a unique thin irreducible $T$-module with
endpoint $0$ and diameter $D$, which we call it the _primary_ $T$-module. The
primary $T$-module has a basis
$E^{*}_{0}\mathbf{j},\ldots,E^{*}_{D}\mathbf{j}$ [87, Lemma 3.6], where
$\mathbf{j}$ is the all-ones vector.

The graph $G$ is said to be _thin with respect to $x$_ whenever every
irreducible $T(x)$-module is thin. The graph $G$ is said to be _thin_ whenever
$G$ is thin with respect to every vertex $x$ of $G$. See [89, Section 6] for
examples of thin $Q$-polynomial distance-regular graphs.

## References

  * [1] R. Aharoni, N. Alon, and E. Berger.  Eigenvalues of ${K}_{1,k}$-free graphs and the connectivity of their independence complexes.  J. Graph Theory, 83(4):384–391, 2016.
  * [2] M. Ajtai, J. Komlós, and E. Szemerédi.  Sorting in $c\log n$ parallel steps.  Combinatorica, 3(1):1–19, 1983.
  * [3] N. Alon.  Eigenvalues and expanders.  Combinatorica, 6(2):83–96, 1986.
  * [4] N. Alon and F. R. K. Chung.  Explicit construction of linear sized tolerant networks.  Discrete Math., 72(1–3):15–19, 1988.
  * [5] I. Balla, F. Dräxler, P. Keevash, and B. Sudakov.  Equiangular lines and spherical codes in Euclidean space.  Invent. Math., 211:179–212, 2018.
  * [6] S. Bang.  Diameter bounds for geometric distance-regular graphs.  Discrete Math., 341(1):253–260, 2018.
  * [7] S. Bang, A. Dubickas, J. H. Koolen, and V. Moulton.  There are only finitely many distance-regular graphs of fixed valency greater than two.  Adv. Math., 269:1–55, 2015.
  * [8] S. Bang, T. Fujisaki, and J. H. Koolen.  The spectra of the local graphs of the twisted Grassmann graphs.  European J. Combin., 30(3):638–654, 2009.
  * [9] S. Bang, E. R. van Dam, and J. H. Koolen.  Spectral characterization of the Hamming graphs.  Linear Algebra Appl., 429(11–12):2678–2686, 2008.
  * [10] F. Belardo, S. M. Cioabă, J. H. Koolen, and J. F. Wang.  Open problems in the spectral theory of signed graphs.  Art Discrete Appl. Math., 1(2):#P2.10, 2018.
  * [11] Y. Bramoullé, R. Kranton, and M. D’Amours.  Strategic interaction and networks.  Am. Econ. Rev., 104(3):898–930, 2014.
  * [12] A. E. Brouwer, A. M. Cohen, and A. Neumaier.  Distance-Regular Graphs.  Springer-Verlag Berlin Heidelberg, 1989.
  * [13] A. E. Brouwer and W. H. Haemers.  Spectra of Graphs.  Springer Heidelberg, 2012.
  * [14] F. C. Bussemaker and A. Neumaier.  Exceptional graphs with smallest eigenvalue $-2$ and related problems.  Math. Comp., 59(200):583–608, 1992.
  * [15] P. J. Cameron, J. M. Goethals, J. J. Seidel, and E. E. Shult.  Line graphs, root systems, and elliptic geometry.  J. Algebra, 43:305–327, 1976.
  * [16] M.-Y. Cao, J. H. Koolen, Y.-C. R. Lin, and W.-H. Yu.  The Lemmens-Seidel conjecture and forbidden subgraphs.  arXiv:2003.07511v1, 2020.
  * [17] X.-M. Cheng, A. L. Gavrilyuk, G. R. W. Greaves, and J. H. Koolen.  Biregular graphs with three eigenvalues.  European J. Combin., 56:57–80, 2016.
  * [18] X.-M. Cheng, G. R. W. Greaves, and J. H. Koolen.  Graphs with three eigenvalues and second largest eigenvalue at most 1\.  J. Combin. Theory Ser. B, 129:55–78, 2018.
  * [19] X.-M. Cheng and J. H. Koolen.  A generalization of a theorem of Neumaier.  Des. Codes Cryptogr., 84:135–142, 2017.
  * [20] M. Chudnovsky and P. Seymour.  The structure of claw-free graphs.  Surveys in Combinatorics, London Math. Soc. Lecture Note Ser., 327:153–172, 2005.
  * [21] M. Chudnovsky and P. Seymour.  Claw-free graphs. I. Orientable prismatic graphs.  J. Combin. Theory Ser. B, 97(6):867–903, 2007.
  * [22] M. Chudnovsky and P. Seymour.  Claw-free graphs. II. Non-orientable prismatic graphs.  J. Combin. Theory Ser. B, 98(2):249–290, 2008.
  * [23] M. Chudnovsky and P. Seymour.  Claw-free graphs. III. Circular interval graphs.  J. Combin. Theory Ser. B, 98(4):812–834, 2008.
  * [24] M. Chudnovsky and P. Seymour.  Claw-free graphs. IV. Decomposition theorem.  J. Combin. Theory Ser. B, 98(5):839–938, 2008.
  * [25] M. Chudnovsky and P. Seymour.  Claw-free graphs. V. Global structure.  J. Combin. Theory Ser. B, 98(6):1373–1410, 2008.
  * [26] M. Chudnovsky and P. Seymour.  Claw-free graphs. VI. Colouring.  J. Combin. Theory Ser. B, 100(6):560–572, 2010.
  * [27] M. Chudnovsky and P. Seymour.  Claw-free graphs. VII. Quasi-line graphs.  J. Combin. Theory Ser. B, 102(6):1267–1294, 2012.
  * [28] S. M. Cioabă, R. J. Elzinga, and D. A. Gregory.  Some observations on the smallest adjacency eigenvalue of a graph.  Discuss. Math. Graph Theory, 40(2):467–493, 2020.
  * [29] S. M. Cioabă, J. H. Koolen, and W. Li.  Disconnecting strongly regular graphs.  European J. Combin., 38:1–11, 2014.
  * [30] S. M. Cioabă, J. H. Koolen, and H. Nozaki.  A spectral version of the Moore problem for bipartite regular graphs.  Algebr. Comb., 2(6):1219–1238, 2019.
  * [31] J. H. Conway and N. J. A. Sloane.  Low-dimensional lattices V. Integral coordinates for integral lattices.  Proc. R. Soc. Lond. A, 426:211–232, 1989.
  * [32] D. Cvetković, M. Doob, and S. Simić.  Generalized line graphs.  J. Graph Theory, 5(4):385–399, 1981.
  * [33] D. Cvetković, P. Rowlinson, and S. Simić.  Spectral Generalizations of Line Graphs: On Graphs with Least Eigenvalue $-2$.  Cambridge Univ. Press, Cambridge, 2004.
  * [34] D. Cvetković, P. Rowlinson, and S. Simić.  Graphs with least eigenvalue $-2$: Ten years on.  Linear Algebra Appl., 484:504–539, 2015.
  * [35] W. Ebeling.  Lattices and Codes: A Course Partially Based on Lectures by F. Hirzebruch.  Friedr. Vieweg & Sohn, Braunschweig, 1994.
  * [36] J. Friedman.  A proof of Alon’s second eigenvalue conjecture and related problems.  Mem. Amer. Math. Soc., 195(910):100pp, 2008.
  * [37] M. Furuya, S. Kubota, T. Taniguchi, and K. Yoshino.  The uniqueness of covers for widely generalized line graphs.  arXiv:2002.08049v1, 2020.
  * [38] A. L. Gavrilyuk and J. H. Koolen.  On a characterization of the Grassmann graphs.  arXiv:1806.02652v1, 2018.
  * [39] A. L. Gavrilyuk and J. H. Koolen.  A characterization of the graphs of bilinear $(d\times d)$-forms over $\mathbb{F}_{2}$.  Combinatorica, 39(2):289–321, 2019.
  * [40] A. L. Gavrilyuk and J. H. Koolen.  On some recent progress in the classification of $({P}$ and ${Q})$-polynomial association schemes.  Arab. J. Math., 2019.
  * [41] A. L. Gavrilyuk, A. Munemasa, Y. Sano, and T. Taniguchi.  Signed analogue of line graphs and their smallest eigenvalues.  arXiv:2003.05578v1, 2020.
  * [42] C. Godsil and K. Meagher.  Erdős–Ko–Rado Theorems: Algebraic Approaches.  Cambridge University Press, Cambridge, 2016.
  * [43] C. Godsil and G. Royle.  Algebraic Graph Theory.  Springer-Verlag, Berlin, 2001.
  * [44] C. D. Godsil.  Geometric distance-regular covers.  New Zealand J. Math., 22:31–38, 1993.
  * [45] G. Greaves, J. Koolen, A. Munemasa, Y. Sano, and T. Taniguchi.  Edge-signed graphs with smallest eigenvalue greater than $-2$.  J. Combin. Theory Ser. B, 110:90–111, 2015.
  * [46] G. Greaves, J. H. Koolen, and J. Park.  Improving the Delsarte bound.  Manuscript, 2020.
  * [47] S. Hayat, J. H. Koolen, and M. Riaz.  A spectral characterization of the $s$-clique extension of the square grid graphs.  European J. Combin., 76:104–116, 2019.
  * [48] A. J. Hoffman.  On spectrally bounded graphs.  A Survey of Combinatorial Theory, pp. 277–283, 1973.
  * [49] A. J. Hoffman.  On graphs whose least eigenvalue exceeds $-1-\sqrt{2}$.  Linear Algebra Appl., 16:153–165, 1977.
  * [50] T. Høholdt and J. Justesen.  On the sizes of expander graphs and minimum distances of graph codes.  Discrete Math., 325:38–46, 2014.
  * [51] S. Hoory, N. Linial, and A. Wigderson.  Expander graphs and their applications.  Bull. Amer. Math. Soc. (N.S.), 43(4):439–561, 2006.
  * [52] H. J. Jang, J. Koolen, A. Munemasa, and T. Taniguchi.  On fat Hoffman graphs with smallest eigenvalue at least $-3$.  Ars Math. Contemp., 7(1):105–121, 2014.
  * [53] D. Jungnickel and V. D. Tonchev.  Polarities, quasi-symmetric designs, and Hamada’s conjecture.  Des. Codes Cryptogr., 51(2):131–140, 2009.
  * [54] H. K. Kim, J. H. Koolen, and J. Y. Yang.  A structure theory for graphs with fixed smallest eigenvalue.  Linear Algebra Appl., 540:1–13, 2016.
  * [55] J. H. Koolen and S. Bang.  On distance-regular graphs with smallest eigenvalue at least $-m$.  J. Combin. Theory Ser. B, 100:573–584, 2010.
  * [56] J. H. Koolen, B. Gebremichel, M. U. Rehman, J. Y. Yang, and Q. Yang.  Sesqui-regular graphs with smallest eigenvalue at least $-3$.  In preparation.
  * [57] J. H. Koolen, B. Gebremichel, and J. Y. Yang.  Sesqui-regular graphs with fixed smallest eigenvalue.  arXiv:1904.01274v1, 2019.
  * [58] J. H. Koolen, Y.-R. Li, and Q. Yang.  On fat Hoffman graphs with smallest eigenvalue at least $-3$, part II.  Linear Algebra Appl., 550:121–143, 2018.
  * [59] J. H. Koolen and A. Munemasa.  The regular two-graph on $276$ vertices revisited.  Manuscript, 2020.
  * [60] J. H. Koolen, M. U. Rehman, and Q. Yang.  The integrally representable trees of norm $3$.  Ann. Math. Sci. Appl., 2(2):385–408, 2017.
  * [61] J. H. Koolen, M. U. Rehman, and Q. Yang.  On the integrability of strongly regular graphs.  Graphs Combin., 35:1273–1291, 2019.
  * [62] J. H. Koolen, J. Y. Yang, and Q. Yang.  On graphs with smallest eigenvalue at least $-3$ and their lattices.  Adv. Math., 338:847–864, 2018.
  * [63] J. H. Koolen and Q. Yang.  Problems on graphs with fixed smallest eigenvalue.  Algebra Colloq., 27(1):51–54, 2020.
  * [64] J. H. Koolen, Q. Yang, and J. Y. Yang.  A generalization of a theorem of Hoffman.  J. Combin. Theory Ser. B, 135:75–95, 2019.
  * [65] J. Krausz.  Démonstration nouvelle d’une théorème de Whitney sur les réseaux (Hungarian).  Mat. Fiz. Lapok, 50:75–85, 1943.
  * [66] M. Krivelevich and B. Sudakov.  Pseudo-random graphs.  More sets, graphs and numbers, Bolyai Soc. Math. Stud., 15:199–262, 2006.
  * [67] S. Kubota, T. Taniguchi, and K. Yoshino.  On graphs with the smallest eigenvalue at least $-1-\sqrt{2}$, part III.  Ars Math. Contemp., 17(2):555–579, 2019.
  * [68] P. W. H. Lemmens and J. J. Seidel.  Equiangular lines.  J. Algebra, 24(3):494–512, 1973.
  * [69] W.-C. W. Li and P. Solé.  Spectra of regular graphs and hypergraphs and orthogonal polynomials.  European J. Combin., 17(5):461–477, 1996.
  * [70] A. Lubotzky, R. Phillips, and P. Sarnak.  Ramanujan graphs.  Combinatorica, 8(3):261–277, 1988.
  * [71] A. W. Marcus, D. A. Spielman, and N. Srivastava.  Interlacing families I: Bipartite Ramanujan graphs of all degrees.  Ann. of Math. (2), 182(1):307–325, 2015.
  * [72] G. A. Margulis.  Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators (Russian).  Probl. Peredachi Inf., 24(1):51–60, 1988.
  * [73] K. Metsch.  A characterization of Grassmann graphs.  European J. Combin., 16(6):639–644, 1995.
  * [74] K. Metsch.  On a characterization of bilinear forms graphs.  European J. Combin., 20(4):293–306, 1999.
  * [75] M. Morgenstern.  Existence and explicit constructions of $q+1$ regular Ramanujan graphs for every prime power $q$.  J. Combin. Theory Ser. B, 62(1):44–62, 1994.
  * [76] A. Munemasa, Y. Sano, and T. Taniguchi.  Fat Hoffman graphs with smallest eigenvalue at least $-1-\tau$.  Ars Math. Contemp., 7(1):247–262, 2014.
  * [77] A. Munemasa, Y. Sano, and T. Taniguchi.  Fat Hoffman graphs with smallest eigenvalue greater than $-3$.  Discrete Appl. Math., 176:78–88, 2014.
  * [78] A. Munemasa and V. D. Tonchev.  The twisted Grassmann graph is the block graph of a design.  Innov. Incidence Geom., 12(1):1–6, 2011.
  * [79] A. Neumaier.  Strongly regular graphs with smallest eigenvalue $-m$.  Arch. Math., 33:392–400, 1979.
  * [80] J.-P. Serre.  Répartition asymptotique des valeurs propres de l’opérateur de Hecke ${T}_{p}$. (French).  J. Amer. Math. Soc., 10(1):75–102, 1997.
  * [81] D. Stevanović.  Spectral Radius of Graphs.  Academic Press, 2015.
  * [82] H. Suzuki.  An introduction to distance-regular graphs, Lecture Note, in Three Lectures in Algebra.  Sophia University Lecture Note Series, 41:57–132, 1999.
  * [83] Y.-Y. Tan, J. H. Koolen, and Z.-J. Xia.  A spectral characterization of the $s$-clique extension of the triangular graphs.  Discuss. Math. Graph Theory, 40:663–676, 2020.
  * [84] T. Taniguchi.  On graphs with the smallest eigenvalue at least $-1-\sqrt{2}$, part I.  Ars Math. Contemp., 1(1):81–98, 2008.
  * [85] T. Taniguchi.  On graphs with the smallest eigenvalue at least $-1-\sqrt{2}$, part II.  Ars Math. Contemp., 5(2):243–258, 2012.
  * [86] P. Terwilliger.  The Johnson graph ${J}(d,r)$ is unique if $(d,r)\neq(2,8)$.  Discrete Math., 58(2):175–189, 1986.
  * [87] P. Terwilliger.  The subconstituent algebra of an association scheme, (part I).  J. Algebraic Combin., 1:363–388, 1992.
  * [88] P. Terwilliger.  Lecture note on Terwilliger algebra (edited by H. Suzuki), 1993\.  https://icu-hsuzuki.github.io/lecturenote/, visited: 13-11-2020.
  * [89] P. Terwilliger.  The subconstituent algebra of an association scheme (part III).  J. Algebraic Combin., 2:177–210, 1993.
  * [90] E. R. van Dam.  Nonregular graphs with three eigenvalues.  J. Combin. Theory Ser. B, 73(2):101–118, 1998.
  * [91] E. R. van Dam, W. H. Haemers, J. H. Koolen, and E. Spence.  Characterizing distance-regularity of graphs by the spectrum.  J. Combin. Theory Ser. A, 113(8):1805–1820, 2006.
  * [92] E. R. van Dam and J. H. Koolen.  A new family of distance-regular graphs with unbounded diameter.  Invent. math., 162(1):189–193, 2005.
  * [93] E. R. van Dam, J. H. Koolen, and H. Tanaka.  Distance-regular graphs.  Electron. J. Combin., Dynamic Surveys:#DS22, 2016.
  * [94] R. Woo and A. Neumaier.  On graphs whose smallest eigenvalue is at least $-1-\sqrt{2}$.  Linear Algebra Appl., 226–228:577–591, 1995.
  * [95] J. Y. Yang and J. H. Koolen.  On the order of regular graphs with fixed second largest eigenvalue.  Linear Algebra Appl., 610:29–39, 2021.
  * [96] Q. Yang, A. Abiad, and J. H. Koolen.  An application of Hoffman graphs for spectral characterizations of graphs.  Electron. J. Combin., 24(1):#P1.12, 2017.
  * [97] H. Yu.  On the limit points of the smallest eigenvalues of regular graphs.  Des. Codes Cryptogr., 65:77–88, 2012.