% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf Distance-regular graphs with an eigenvalue\\ $-k<\theta \leq 2-k$}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Sejeong~Bang\thanks{Supported by NRF grant NRF-2011-001-3985.}\\
\small Department of Mathematics\\[-0.8ex]
\small Yeungnam University\\[-0.8ex] 
\small Gyeongsan-si Republic of Korea\\
\small\tt sjbang@ynu.ac.kr
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{X, 2013}{X,X}\\
\small Mathematics Subject Classifications: 05C50, 05E30}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
 It is known that bipartite distance-regular graphs with diameter $D\geq 3$, valency $k\geq 3$, intersection number $c_2\geq 2$ and eigenvalues $k=\theta_0>\theta_1>\cdots >\theta_D$ satisfy $\theta_1\leq  k-2$
and thus $\theta_{D-1}\geq 2-k$. In this paper we classify non-complete distance-regular graphs with valency $k\geq 2$, intersection number $c_2\geq 2$ and an eigenvalue $\theta$ satisfying $-k< \theta \leq 2-k$
(Theorem \ref{main}). Moreover, we give a lower bound for valency $k$ which implies $\theta_D\geq 2-k$ for distance-regular graphs with girth $g\geq 5$ satisfying $g=5$ or $g\equiv 3~(mod~4)$. 

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} Distance-regular graph; Girth; Smallest eigenvalue; Folded ($2D+1$)-cube
\end{abstract}

\section{Introduction}
Let $\Gamma$ be a distance-regular graph with diameter $D\geq 3$
and eigenvalues $k=\theta_0>\theta_1>\cdots > \theta_D$. It is
shown in \cite[Theorem 4.4.3 (ii)]{bcn} that if $c_2\geq 2$ then either $\Gamma$ is the icosahedron or $\Gamma$ satisfies $\theta_1\leq
b_1-1$. Distance-regular graphs with $c_2\geq 2$ and
$\theta_1=b_1-1$ are classified (see \cite[Theorem 4.4.11]{bcn}).
In particular, any non-complete bipartite distance-regular graph $\Gamma$ with valency $k\geq 2$, intersection number $c_2\geq 2$ and an eigenvalue $\theta$ with $-k<\theta \leq  2-k$ satisfies $\theta=2-k$ and $\Gamma$ is either the cycle of length four or the Hamming $D$-cube by $2-k\leq -\theta_1\leq \theta\leq 2-k$
and \cite[Theorem 4.4.11]{bcn}. \\

In the following theorem we classify non-complete distance-regular graphs with valency $k\geq 2$, intersection number $c_2\geq 2$ and an eigenvalue $\theta$ satisfying $-k< \theta \leq 2-k$.

\begin{theorem}\label{main}
Let $\Gamma$ be a distance-regular graph with diameter $D\geq 2$, valency $k\ge 2$ and intersection number $c_2\geq 2$. If there exists an eigenvalue
$\theta$ of $\Gamma$ satisfying $-k<\theta \leq 2-k$ then $\theta=2-k$ and $\Gamma$ is one of the following:\\
(i) the cycle of length four, \\
(ii) the Johnson graph $J(4,2)$,\\
(iii) the $3\times 3$-grid,\\
(iv) the Hamming $D$-cube $H(D,2)$, or\\
(v) the folded $(2D+1)$-cube.
\end{theorem}
The folded $n$-cube $(n\neq 6)$ is uniquely characterized by its intersection array (cf. \cite[Theorem 9.2.7]{bcn}). It follows by Theorem \ref{main} that a distance-regular graph with $D\geq 3$, $k\geq 3$, $c_2\geq 2$ and an eigenvalue $\theta$ satisfying
$-k< \theta \leq 2-k$ is either the Hamming $D$-cube or the folded $(2D+1)$-cube.\\
A distance-regular graph $\Gamma$ with diameter $D\geq 3$ and girth $g=3$ is either the icosahedron or $\Gamma$ satisfies
$\theta_D\geq -\frac{b_1}{2}-1$ (cf. \cite[Theorem 4.4.3 (iii)]{bcn}). Distance-regular graphs with $a_1\geq 2$ and $\theta_D=-\frac{b_1}{2}-1$ are
classified in \cite{-1-b/2} (see also \cite{k-y}). There are non-complete distance-regular graphs with girth $g\geq 4$ and an eigenvalue $\theta$
satisfying $-k<\theta < -\frac{b_1}{2}-1$, such as the Hamming $D$-cube ($D\geq 6$) and the folded $(2D+1)$-cube ($D\geq 3$)
which have $2-k$ as an eigenvalue. If $g =4$ then any eigenvalue $\theta\neq -k$ satisfies $\theta \geq 2-k$ (see Theorem \ref{main}).\\
In Theorem \ref{g=5} and Theorem \ref{g=3(mod4)thm} we study distance-regular graphs with girth $g \geq 5$ satisfying either $g =5$ or $g \equiv 3~(mod~4)$, and give a lower bound for valency $k$ which implies $\theta_D\geq 2-k$ by considering a lower bound for $\frac{\theta_D}{k}$.

\begin{theorem}\label{g=5}
Let $\Gamma$ be a distance-regular graph with diameter $D\geq 2$, valency $k\geq 3$ and girth $g =5$. Then the smallest eigenvalue $\theta_D$ of $\Gamma$ satisfies
\begin{equation}\label{g=5'}
\theta_D\ge \left(\frac{1-\sqrt{73}}{9}\right)k.
\end{equation}
In particular, if $k\geq 10$ then $\theta_D>2-k$.
\end{theorem}


\begin{theorem}\label{g=3(mod4)thm}
Let $\Gamma$ be a distance-regular graph with diameter $D\geq 3$, valency $k\geq 3$ and girth $g >3$ satisfying $g \equiv 3~(mod~4)$. Then there exist real numbers $C(g)\ge 3$ and $\gamma(g)\in (-1,-0.64)$ (depending only on $g$) such that if $k\ge C(g)$ then the smallest eigenvalue
$\theta_D$ satisfies
\[\theta_D \ge \gamma(g) k.\]
In particular, if $k\geq \max\left\{ C(g), \frac{2}{\gamma(g) +1} \right \}$ then $\theta_D\geq 2-k$.
\end{theorem}


The paper is organized as follows. In Section 2 we review some definitions and basic concepts. In Section 3 we prove  Theorem \ref{main}. In the last section we prove Theorem \ref{g=5} and Theorem \ref{g=3(mod4)thm}. As an example of Theorem \ref{g=3(mod4)thm}, we will consider the case $g = 7$ (see Example \ref{exag=7}).

\section{Preliminaries}
All the graphs considered in this paper are finite, undirected and
simple. The reader is referred to \cite{bcn} for more background information. For a connected graph $\Gamma=(V(\Gamma),E(\Gamma))$, the distance $d(x,y)$
between two vertices $x,y$ of $\Gamma$ is the length of a shortest
path between $x$ and $y$ in $\Gamma$, and the diameter $D$ is the
maximum distance between any two vertices of $\Gamma$. For any vertex $x\in V(\Gamma)$, let $\Gamma_i(x)$ be the set of vertices in
$\Gamma$ at distance $i$ from $x$ ($0\leq i\leq D$). The {\em adjacency matrix} $A$ is the
$|V(\Gamma)|\times |V(\Gamma)|$-matrix with rows and columns indexed by $V(\Gamma)$, where the $(x,y)$-entry of $A$ equals $1$
whenever $d(x,y)=1$ and $0$ otherwise. The eigenvalues of $\Gamma$ are the eigenvalues of $A$. The {\em girth} of $\Gamma$, denoted by $g$,
is the length of a shortest cycle in $\Gamma$. A connected graph $\Gamma$ is called a {\em distance-regular graph}~if there exist integers $b_i$, $c_i$, $i=0,1,\ldots,D$,
such that for any two vertices $x,y$ at distance $i=d(x,y)$, there are
precisely $c_i$ neighbors of $y$ in $\Gamma_{i-1}(x)$ and $b_i$
neighbors of $y$ in $\Gamma_{i+1}(x)$. In particular, $\Gamma$ is
regular with valency $k:=b_0$. The numbers $b_i, c_i$ and
$a_i:=k-b_i-c_i~(0\leq i\leq D)$ are called the {\em
intersection numbers} of $\Gamma$. Set $c_0=b_{D}=0$. We observe $a_0=0$ and $c_1=1$. The array
\[
\iota(\Gamma)=\{b_0,b_1,\ldots,b_{D-1};c_1,c_2,\ldots,c_{D}\}
\]
is called the {\em intersection array} of $\Gamma$. The intersection numbers satisfy the following restrictions
\[1=c_1\leq c_2\leq \cdots \leq c_D\leq k \mbox{~~and~~} k=b_0 \geq b_1 \geq \cdots \geq b_{D-1}\geq 1\]
(cf. \cite[Proposition 4.1.6]{bcn}). The following inequalities for intersection numbers of a distance-regular graph will be used in Section $3$.

\begin{lemma} (\cite[Proposition 5.5.4 (ii)]{bcn})\label{554}
Let $\Gamma$ be a distance-regular graph with diameter $D\geq 2$. Suppose that $a_i\ne 0$ for some $1\leq i\leq D$, and define $a_{D+1}=0$.
If $i>1$ then $c_i\leq a_i +\frac{a_{i-1} c_i}{a_i}$, and for $i<D$ equality implies $a_{i+1}=a_i$.
\end{lemma}
Suppose that $\Gamma$ is a distance-regular graph~with diameter $D\geq 2$ and valency $k\geq 2$. We define $k_i:=|\Gamma_i(x)|$ for any vertex
$x$ and $i=0,1,\ldots,D$. Then we have
\[
k_0=1,~~k_1=b_0,~~k_{i+1}=\frac{k_i b_i}{c_{i+1}} ~~(i=0,1,\ldots,D-1).
\]
It is known that $\Gamma$ has
exactly $D+1$ distinct eigenvalues which are the eigenvalues of the tridiagonal matrix
\[
 L_1(\Gamma):= \left\lgroup
 \begin{tabular}{llllllll}
 $0$ & $b_0$\\
 $c_1$ & $a_1$ & $b_1$\\
 & $c_2$ & $a_2$ & $b_2$\\
 & & . & . & .\\
 & & & $c_i$ & $a_i$ & $b_i$\\
 & & & & . & . & .\\
 & & & & & $c_{D-1}$ & $a_{D-1}$ & $b_{D-1}$\\
& & & & &\makebox{\hspace{.324cm}} &
 $c_{D}$ & $a_{D}$
 \end{tabular}
 \right\rgroup
\]
(cf. \cite[p.128]{bcn}).
Let $k=\theta_0>\theta_1>\cdots >\theta_D$ be the $D+1$ distinct eigenvalues of $\Gamma$. A {\em clique} is a set of pairwise adjacent vertices.
Any clique $C$ in $\Gamma$ satisfies
\begin{equation}\label{hoffman-bd}
|C|\leq 1-\frac{k}{\theta_D}
\end{equation}
(see \cite[Proposition 4.4.6 (i)]{bcn}). The {\em standard sequence} $u_i=u_i(\theta)~ (0 \leq i\leq D)$
corresponding to an eigenvalue $\theta$ is a sequence satisfying $u_0= 1$,
$u_1= \frac{\theta}{k}$ and
\begin{equation}\label{3-term-rec}
c_iu_{i-1} + a_iu_i + b_iu_{i+1} = \theta u_i ~~(1 \leq i \leq D)
\end{equation}
(cf. \cite[p. 128]{bcn}). The multiplicity of eigenvalue $\theta$ is given by
\[
m (\theta)=\frac{|V(\Gamma)|}{\sum_{i=0}^{D}k_iu_i^2(\theta)}
\]
which is known as {\em Biggs' formula} (cf. \cite[Theorem 21.4]{biggs}, \cite[Theorem 4.1.4]{bcn}). Let $\theta\ne k$ be an eigenvalue of $\Gamma$ with
multiplicity $m=m(\theta)$. Then there exists a map $\rho : V(\Gamma) \rightarrow \mathbb{R}^m$ such that\\
(i) $\sum _{x\in V(\Gamma)} \rho(x)=0$ and\\
(ii) for any two vertices $x,y$ with $d(x,y)=i$, the inner product satisfies $\langle \rho(x),\rho(y)\rangle=u_{i}(\theta)$\\
where $\mathbb{R}$ is the real numbers (see \cite[Proposition 4.4.1]{bcn}). The map $\rho$ is called the
{\em standard representation} of $\Gamma$ corresponding to $\theta$.

\section{Proof of Theorem \ref{main}}

In this section we classify distance-regular graphs with intersection numbers $a_1$ and $c_2$ satisfying $(a_1,c_2)\ne (0,1)$ and an eigenvalue $\theta$ satisfying
$-k<\theta\leq 2-k$. We first consider distance-regular graphs with $a_1\geq 1$. Using the classification of distance-regular graphs with valency four
by Brouwer and Koolen \cite{k=4}, we obtain the following lemma.

\begin{lemma}\label{tri-lemma}
Let $\Gamma$ be a distance-regular graph with diameter $D\geq 2$, valency $k\ge 3$ and intersection number $a_1\geq 1$.
If the smallest eigenvalue $\theta_D$ satisfies $\theta_{D} \leq 2-k$ then $k=4$ and $\Gamma$ is one of the following:\\
(i) the Johnson graph $J(4,2)$ with $\iota(\Gamma)=\{4,1;1,4\}$,\\
(ii) the $3\times 3$-grid with $\iota(\Gamma)=\{4,2;1,2\}$,\\
(iii) the line graph of Petersen graph with $\iota(\Gamma)=\{4,2,1;1,1,4\}$,\\
(iv) the flag graph of PG(2,2) with $\iota(\Gamma)=\{4,2,2;1,1,2\}$,\\
(v) the flag graph of GQ(2,2) with $\iota(\Gamma)=\{4,2,2,2;1,1,1,2\}$, or\\
(vi) the flag graph of GH(2,2) with $\iota(\Gamma)=\{4,2,2,2,2,2;1,1,1,1,1,2\}$.
\end{lemma}

\begin{proof} 
Suppose that $\theta_D$ satisfies $\theta_{D} \leq 2-k$. By $a_1\geq 1$ and (\ref{hoffman-bd}), each clique $C$ in $\Gamma$ satisfies
\[3\leq |C| \leq 1-\frac{k}{\theta_{D}}\leq 1+\frac{k}{k-2}.\]
Hence we find $k\leq 4$. Since there are no distance-regular graphs satisfying $D\geq 2$, $k= 3$ and $a_1\geq 1$, we obtain $k=4$ and thus the result
follows by \cite[Theorem 1.1]{k=4}.
\end{proof}

Using \cite[Proposition 4.4.9 (i)]{bcn}, we obtain Lemma \ref{ter} (i). The result Lemma \ref{ter} (ii) is shown by Terwilliger (\cite{ter-quadrangle}, cf. \cite[Theorem 5.2.1]{bcn}).

\begin{lemma}\label{ter}
Let $\Gamma$ be a distance-regular graph with diameter $D\ge 2$.
If $\Gamma$ contains an induced quadrangle then the following hold.\\
(i) For any eigenvalue $\theta$, $u_0(\theta)+2u_1(\theta)+u_2(\theta) \ge 0.$\\
(ii) For each $i=1,2,\ldots,D$, $c_i-b_i\ge c_{i-1}-b_{i-1}+a_1+2.$
\end{lemma}

\begin{proof} 
Suppose that $\Gamma$ contains an induced quadrangle, say $Q=x_0x_1x_2x_3$ where
$d(x_i,x_{i+1})=1=d(x_0,x_3)~i=0,1,2$. \\
(i): Let $\rho$ be the standard
representation of $\Gamma$ corresponding to an eigenvalue $\theta$, and put $\alpha:=\rho(x_0)+\rho(x_2)$ and
$\beta:=\rho(x_1)+\rho(x_3)$. Then the result (i) follows from $$0\leq \langle \alpha+\beta,
\alpha+\beta \rangle=\langle \alpha,\alpha \rangle+2 \langle \alpha,\beta \rangle+ \langle \beta,\beta \rangle=4(u_0(\theta)+2u_1(\theta)+u_2(\theta)).$$
(ii): This result is shown by Terwilliger (\cite{ter-quadrangle}, cf. \cite[Theorem 5.2.1]{bcn}).
\end{proof}


To complete the proof of Theorem \ref{main}, we consider triangle-free distance-regular graphs in Lemma \ref{ev for triangle-free} and Lemma \ref{quadrangle-bd}. If $\Gamma$ contains an induced
quadrangle then the inequality $u_0(\theta)-2u_1(\theta)+u_2(\theta) \ge 0$ in \cite[Proposition 4.4.9 (i)]{bcn} is equivalent to either $\theta =k$ or $\theta \leq b_1-1$. In the following lemma we consider an equivalent condition to
the inequality $u_0(\theta)+2u_1(\theta)+u_2(\theta) \ge 0$ of Lemma \ref{ter} (i) when $\Gamma$ is a non-complete triangle-free distance-regular graph.


\begin{lemma}\label{ev for triangle-free}
Let $\Gamma$ be a triangle-free distance-regular graph with diameter $D\ge 2$ and valency $k\ge 2$. For an eigenvalue
$\theta$ of $\Gamma$, $u_0(\theta)+2u_1(\theta)+u_2(\theta) \ge 0$ holds if and only if
$\theta=-k$ or $\theta \ge 2-k$.
\end{lemma}

\begin{proof}
Let $\theta$ be an eigenvalue of $\Gamma$. It follows by $(c_1,a_1,b_1)=(1,0,k-1)$ and (\ref{3-term-rec}) that $u_0(\theta)+2u_1(\theta)+u_2(\theta)=\frac{(\theta+k)(\theta+k-2)}{k(k-1)}$,
from which the result follows as $\theta\geq -k$.
\end{proof}

\begin{lemma}\label{quadrangle-bd}
Let $\Gamma$ be a triangle-free distance-regular graph with diameter $D\ge 2$ and valency $k\ge 2$. If $\Gamma$ contains an induced quadrangle and
$2-k$ is an eigenvalue of $\Gamma$ then the following hold.\\
(i) $u_i(2-k)=(-1)^i\left(1-\frac{2i}{k}  \right)  ~~(0\le i\le D).$\\
(ii) $(k-1-2i)~a_i=2(c_i-i)~~~(1\le i\le D).$
\end{lemma}

\begin{proof} 
Suppose that $\Gamma$ contains an induced quadrangle and
$2-k$ is an eigenvalue of $\Gamma$. Let $\rho$ be the standard
representation of $\Gamma$ corresponding to eigenvalue $2-k$, and let $Q=x_0x_1x_2x_3$ be an induced quadrangle where
$d(x_i,x_{i+1})=1=d(x_0,x_3)~i=0,1,2$. Put $\alpha:=\rho(x_0)+\rho(x_2)$ and
$\beta:=\rho(x_1)+\rho(x_3)$.\\
(i): Using (\ref{3-term-rec}) with $\theta=2-k$ and $(c_1,a_1,b_1)=(1,0,k-1)$, we find $u_0(2-k)+2u_1(2-k)+u_2(2-k)=0$ and thus
$\alpha+\beta=0$ follows from $$\langle \alpha+\beta,
\alpha+\beta \rangle=\langle \alpha,\alpha \rangle+2 \langle \alpha,\beta \rangle+ \langle \beta,\beta \rangle=4(u_0(\theta)+2u_1(\theta)+u_2(\theta))=0.$$
As $\alpha +\beta =0$ and $\Gamma_{i+2}(x_0)\cap
\Gamma_i(x_2)\subseteq \Gamma_{i+1}(x_1)\cap \Gamma_{i+1}(x_3)~(i=0,1,\ldots,D-2)$, the following holds for each vertex
$v\in \Gamma_{i+2}(x_0)\cap \Gamma_i(x_2)~(i=0,1,\ldots,D-2)$:
\begin{equation}\label{ui(2-k)pf}
0=\langle \alpha+\beta,\rho(v) \rangle=u_i(2-k)+2u_{i+1}(2-k)+u_{i+2}(2-k).
\end{equation}
As $u_0(2-k)=1$ and $u_1(2-k)=\frac{2-k}{k}$, (i) follows from (\ref{ui(2-k)pf}).\\
(ii): It follows by (\ref{3-term-rec}) with $\theta=2-k$ that $c_i u_{i-1}(2-k)+(a_i-2+k) u_i(2-k)+(k-a_i-c_i) u_{i+1}(2-k)=0$, and this shows the result by Lemma \ref{quadrangle-bd} (i).
\end{proof}

We now classify non-complete distance-regular graphs with $k\geq 2$, $c_2\geq 2$ and an eigenvalue $\theta$ satisfying $-k< \theta \leq 2-k$.

\begin{proof}[Proof of Theorem~\ref{main}]
Suppose that $\theta$ is an eigenvalue of $\Gamma$ satisfying $-k<\theta \leq 2-k$. If $\Gamma$ is bipartite then there is an induced quadrangle
as $c_2\geq 2$. By Lemma \ref{ter} (i) and Lemma \ref{ev for triangle-free},  $\theta=2-k=1-b_1=\theta_{D-1}=-\theta_1$. By \cite[Theorem 4.4.11]{bcn}, $\Gamma$ is either (i) or (iv).\\
In the rest of the proof, we assume that $\Gamma$ is not bipartite and put
$$m:=\min\{i\mid a_i\geq 1,~1\leq i \le D \}.$$
Then $1\leq m\leq D$. If $m=1$ then it follows by Lemma \ref{tri-lemma} that $\theta=2-k=-2$ and $\Gamma$ is either (ii) or (iii).
Now suppose $2\leq m\leq D$. As $c_2\geq 2$ and $m \geq 2$, $\Gamma$ contains an induced quadrangle. By Lemma \ref{ter} (i) and Lemma \ref{ev for triangle-free},
\begin{equation}\label{theta}
\theta =2-k.
\end{equation}
We first show the following claim.
\begin{claim}\label{cl1}
$m= D$
\end{claim}

\begin{proof} [Proof of Claim \ref{cl1}]
Assume $2\leq m\leq D-1$. Then by Lemma \ref{554},
\begin{equation}\label{554-}
c_m\leq a_m \mbox{~and~the~equality~implies~~} a_{m+1}=a_m.
\end{equation}
By (\ref{theta}), $m\geq 2$ and Lemma \ref{quadrangle-bd} (ii), we find
\begin{equation}\label{m<d}
  (k-1-2m)a_m=2(c_m-m).
\end{equation}
Using Lemma \ref{ter} (ii) with $a_i=0~(1\leq i\leq m-1)$ we have $c_{i}\geq c_{i-1} +1~(1\leq i\leq m-1)$ and thus
$c_m\geq c_{m-1}\geq m-1$ follows. If $c_{m}=m-1$ then it follows by (\ref{554-}) and (\ref{m<d}) that $2\leq c_2 \leq m-1=c_m\leq a_m\leq 2$ and thus $m=3$, $k=6$ and $a_{m+1}=a_m=2$.
The case $i=m+1=4$ of Lemma \ref{quadrangle-bd} (ii) implies $c_4=c_{m+1}=1$ which is impossible as $c_4\geq c_2\geq 2$.
Hence we find $c_m\geq m$ and thus $k\geq 2m+1$ from (\ref{m<d}). On the other hand, $2(c_m-m)=a_m(k-1-2m)\ge c_m(k-1-2m)$ holds by (\ref{554-}) and (\ref{m<d}). Hence we find $2c_m\leq c_m +a_m \leq k\le 2m+2$ and thus $c_m\in \{ m,m+1\}$.
If $c_m=m+1$ then $(c_m,a_m,b_m)=(m+1,m+1,0)$, which contradicts to $m\leq D-1$.
Hence $c_m=m$ and thus $k=2m+1$ and $m=c_m=a_m=a_{m+1}$ by (\ref{554-}) and (\ref{m<d}). The equation of Lemma \ref{quadrangle-bd} (ii) with $i=m+1$
yields $c_{m+1}=1$. This is also impossible as $c_{m+1}\geq c_2\geq 2$. Hence $m=D$.
\end{proof}

By Lemma \ref{quadrangle-bd} (ii), Claim \ref{cl1} and (\ref{theta}), $a_i=0$ and $c_i=i$ for all $i=1,2,\ldots,D-1$, i.e.,
$$\iota(\Gamma)=\{k,k-1,\ldots,k-D+2,k-D+1;1,2,\ldots,D-1,c_D \}.$$
Note here that $k\neq 2D-1$ otherwise we have $D=a_D+c_D=k=2D-1$ by Lemma \ref{quadrangle-bd} (ii) with $i=D$, which contradicts to the condition
$D\geq 2$. Applying Lemma \ref{quadrangle-bd} (ii) with $i=D$, we have
\begin{equation}\label{c_D}
c_D=\frac{(k-2D)(k-1)}{k-2D+1}.
\end{equation}

Since we have $a_D\ge c_D \ge c_{D-1}=D-1$ by Lemma \ref{554}, we find $\max\{2,D-1\} \leq c_D \leq \frac{k}{2}$
which implies $k\geq 4$ and $2(D-1)\leq k \leq 2D+ 2$ by (\ref{c_D}). Moreover, it follows by $a_D\geq c_D$, Lemma \ref{quadrangle-bd} (ii) and (\ref{c_D})
that $k=2D+1$ and $c_D=D$. Therefore $\Gamma$ has the same intersection array with the folded $(2D+1)$-cube,
\[\iota(\Gamma)=\{2D+1,2D,\ldots,D+3,D+2 ; 1,2,\ldots,D\}.\]
As the folded $(2D+1)$-cube is uniquely determined by its
intersection numbers (cf. \cite[Theorem 9.2.7]{bcn}), $\Gamma$ is
the folded $(2D+1)$-cube. This completes the proof of Theorem \ref{main}.\end{proof}


\section{Proofs of Theorem \ref{g=5} and Theorem \ref{g=3(mod4)thm}}

In this section we consider lower bounds for the smallest eigenvalue of a distance-regular graph with girth $g \in \{ 5, 4s-1 \mid s\geq 2\}$.\\

Let $\Gamma$ be a distance-regular graph with diameter $D\geq 3$ and girth $g =3$. Then by \cite[Theorem 4.4.3 (iii)]{bcn}, $\Gamma$ is either the icosahedron or $\Gamma$
satisfies $\theta_D\geq -\frac{b_1}{2}-1$. For both cases, the smallest eigenvalue $\theta_D$ satisfies $\theta_D \geq -\frac{1}{2}k$.
In Theorem \ref{g=5} and Theorem \ref{g=3(mod4)thm} we consider a lower bound for $\frac{\theta_D}{k}$ using girth $g$ if $g >3$ satisfies $g =5$ or $g \equiv 3~(mod~4)$, and give a lower bound for valency $k$ which implies $\theta_D\geq 2-k$.

We first consider distance-regular graphs with girth $g=5$ and prove Theorem \ref{g=5}.

\begin{proof}[Proof of Theorem~\ref{g=5}]
Let $P=x_0 x_1 x_2 x_3 x_4$ be an induced pentagon in $\Gamma$ where $d(x_i,x_{i+1})=1=d(x_0,x_4), i=0,1,2,3$. For the smallest eigenvalue $\theta=\theta_D$, let $\rho$ be the corresponding standard representation and put $\alpha :=(\rho(x_0)+\rho(x_1)+\rho(x_4))-(\rho(x_2)+\rho(x_3))$.
Then
\begin{equation}\label{g=5-sol}
\frac{k-1-\sqrt{31k^2+4k+1}}{6}\le \theta\le k <\frac{k-1+\sqrt{31k^2+4k+1}}{6}
\end{equation}
follows by
\[
0\le  \langle \alpha, \alpha \rangle=5u_0(\theta)+2u_1(\theta)-6u_2(\theta)
= \frac{-1}{k(k-1)}\left\{6\theta^2+2(-k+1)\theta-k(5k+1)\right\}.
\]
As the function $C(k):=\frac{7k-1-\sqrt{31k^2+4k+1}}{6k}$ is an
increasing function on $k\geq 3$ and $C(3)=\frac{10-\sqrt{73}}{9}$, Inequality (\ref{g=5'}) follows by (\ref{g=5-sol}) and
\[\theta \ge \frac{k-1-\sqrt{31k^2+4k+1}}{6}=-k+C(k)k\geq -k+C(3)k = \left(\frac{1-\sqrt{73}}{9}\right) k~. \]
In particular, $\theta \geq \frac{k-1-\sqrt{31k^2+4k+1}}{6}>2-k$ holds for all $k\geq 10$. This completes the proof.
\end{proof}

To prove Theorem \ref{g=3(mod4)thm}, we first need the following lemma.

\begin{lemma}\label{P_s}
For each integer $s\geq 2$, let $F_{s}(x)=2x^{2s-1}+2x^{2s-2}+\cdots+2x^{2}+2x+1$ and let $z_s$ be the smallest zero of the function $F_s(x)$. Then\\
(i) $-0.65< z_2<-0.64 $.\\
(ii) $F_s(-1)=-1$ and $F_s(0)=1$ for each $s\geq 2$.\\
(iii) $-1<z_{s+1}<z_s<-0.64$ for each $s\geq 2$.
\end{lemma}
\begin{proof} 
(i)-(ii): It is straightforward.\\
(iii): Let $s\geq 2$ be an integer. As $F_{s+1}(x)=2 x+1 + \sum_{i=1}^{s} 2 x^{2i} (x+1)$,
$$F_{s+1}(-1-\epsilon)<2(-1-\epsilon )+1=-1-2\epsilon<0$$ holds for any $\epsilon>0$. Hence $-1< z_{s+1}<0$ follows by (ii).
On the other hand, we find $F_{s+1}(z_s)=z_s^2 F_s(z_s)+(z_s+1)^2=(z_s+1)^2>0$ as $F_{s+1}(x)=x^2 F_s(x)+(x+1)^2$. This shows $z_{s+1}<z_s$ and thus (iii) follows by (i).
\end{proof}

Let $\Gamma$ be a distance-regular graph with girth $g > 3$. Then $(c_i,a_i,b_i)=(1,0,k-1)$ for all $i=1,\ldots, \left\lfloor \frac{g}{2} \right\rfloor-1$. For an eigenvalue $\theta$ of $\Gamma$, it follows by (\ref{3-term-rec}) that
\begin{equation}\label{ui-poly}
k(k-1)^{i-1}u_i(\theta)=\theta^i + \sum_{0\leq \ell+n\leq i-1} t_{(\ell,n)}k^\ell \theta^n ~~~ \left(1 \le i\le \left\lfloor \frac{g}{2} \right\rfloor \right)
\end{equation}
where $t_{(\ell,n)}\in \mathbb{R}$ for all $0\leq \ell+n\leq i-1\leq  \left\lfloor \frac{g}{2} \right\rfloor-2$.

\begin{proof}[Proof of Theorem~\ref{g=3(mod4)thm}]
Let $\rho$ be the standard representation of $\Gamma$ corresponding to the smallest eigenvalue $\theta=\theta_D$. As $g \equiv 3~(mod~4)$ and $g > 3$, let $g =4s-1$
for some $s\geq 2$. Suppose that $P=x_0 x_1\ldots x_{4s-2}$ is an induced polygon of length $4s-1$, where $d(x_i, x_{i+1})=1=d(x_0, x_{4s-2})$
$i=0,1,\ldots,4s-3$. Put $\alpha:=\sum_{i=0}^{4s-2}\rho(x_i)$. Then we have
\begin{equation}\label{g=4s-1}
0 \le \frac{k(k-1)^{2s-2}}{(4s-1) k^{2s-1}} \langle \alpha, \alpha \rangle=\frac{k(k-1)^{2s-2}}{k^{2s-1}}\left(u_0(\theta)+2\sum_{i=1}^{2s-1}u_i (\theta) \right).
\end{equation}
Using (\ref{ui-poly}), Inequality (\ref{g=4s-1}) is equivalent to
\begin{equation}\label{4s-1-eq}
F_s\left(\frac{\theta}{k}\right)\ge
\frac{1}{k^{2s-1}}G_s(k,\theta)
\end{equation}
 where
$F_{s}(x)=2x^{2s-1}+2x^{2s-2}+\cdots+2x^{2}+2x+1$ and $G_s(k,\theta)=\sum_{0\le i+j\le 2s-2} c_{(i,j)}k^i\theta^j$ for some real numbers $c_{(i,j)}$. Hence it follows by $|\theta |<k$ that
\[
\lim _{k\rightarrow \infty}\frac{G_s(k,\theta)}{k^{2s-1}}=0.
\]
Thus there exists a positive integer $C(g)\ge 3$ such
that if $k\ge C(g)$ then $\frac{G_s(k,\theta)}{k^{2s-1}}\ge -\frac{1}{2}$ holds. Note here that for any real number $x$,
\[F_s'(x)=2 s x^{2s-2}+2 (x+1)^2 \sum_{i=1}^{s-1} (s-i) x^{2(s-1-i)}>0.\]
Hence it follows by Lemma \ref{P_s} (ii)-(iii) and Equation (\ref{4s-1-eq}) that $F_s(\frac{\theta}{k})\ge  -\frac{1}{2}$ and there exists a real number
$\gamma(g)\in (-1,z_s)$  satisfying $\frac{\theta}{k}\ge \gamma(g)$. As $-1<\gamma(g)<z_s\leq z_2<-0.64$ holds by Lemma \ref{P_s} (iii),
the result follows. \end{proof}

As an example of Theorem \ref{g=3(mod4)thm}, we will give a lower bound $-0.86$ for $\frac{\theta_D}{k}$ if $g =7$.

\begin{example}\label{exag=7}
Let $\Gamma$ be a distance-regular graph  with diameter $D\geq 3$, valency $k\ge 3$ and girth $g=7$. Then the smallest eigenvalue $\theta_D$ of $\Gamma$ satisfies
\[\theta_D> -0.86 k.\]
In particular, if $k\geq 15$ then $\theta_D > 2-k$.
\end{example}

\begin{proof}
As $g=7$, we have $g=4s-1=7$ with $s=2$. Suppose that $P=x_0x_1\ldots x_{6}$ is an
induced polygon of length $7$, where $d(x_i, x_{i+1})=1=d(x_0, x_{6})$ $i=0,1,\ldots, 5$. For the smallest eigenvalue $\theta=\theta_D$, let $\rho$ be the corresponding standard representation and let $\alpha:=\sum_{i=0}^{6}\rho(x_i)$. It follows by (\ref{3-term-rec}) and (\ref{ui-poly}) that
\begin{eqnarray*}
0&\le& \frac{k(k-1)^{2}}{7 k^{3}} \langle \alpha, \alpha \rangle=\frac{k(k-1)^2}{k^3}\left( u_0(\theta)+2u_1(\theta)+2u_2(\theta)+2u_3(\theta)\right )\\
&=&\frac{1}{k^3}\{k^3+2k^2(\theta-2)+k(2\theta^2-8\theta+3)+2\theta(\theta^2-\theta+2)\}
\end{eqnarray*}
which is equivalent to
\[F_2\left(\frac{\theta}{k}\right)\ge
\frac{1}{k^3}(2\theta^2+8k\theta-4\theta+4k^2-3k):=\frac{1}{k^3}G_2(k,\theta)\]
where $F_2(x)=2x^3+2x^2+2x+1$. In particular, if $k\ge 4$ then
$\frac{G_2(k,\theta)}{k^3}> -\frac12$ as $|\theta |<k$ and
\[2 G_2(k,\theta) +k^3 = 4\theta^2+(16k-8)\theta+(k^3+8k^2-6k)>k(k^2-4k+2)>0.\]
Since $x>-0.86$ follows by $F_2(x)=2x^3+2x^2+2x+1\ge -\frac12$, this shows that if $k\geq 4$ then $\theta>-0.86k$. If $k=3$ then
\[0\le
\frac{4 \langle \alpha, \alpha \rangle}{63}=\frac{4}{9}\left( u_0(\theta)+2u_1(\theta)+2u_2(\theta)+2u_3(\theta)\right )=
\frac{2 \theta(\theta+1+\sqrt{2})(\theta+1-\sqrt{2})}{27},\]
which shows $\theta \ge -1-\sqrt{2}>-0.86\times 3$. In particular, $\theta>-0.86 k \geq 2-k$ holds for all $k\geq 15$. This completes the proof.\end{proof}

\begin{remark}
There are distance-regular graphs $\Gamma$ with girth $g \geq 6$ satisfying $g \equiv 1~(mod~4)$ or $g \equiv 0~(mod~2)$ and an eigenvalue
$\theta$ satisfying $-k<\theta\leq 2-k$, such as the Biggs-Smith graph with intersection array $\iota(\Gamma)=\{3,2,2,2,1,1,1;1,1,1,1,1,1,3 \}$,
the odd graph on $13$ points with $\iota(\Gamma)=\{7,6,6,5,5,4;1,1,2,2,3,3 \}$ and the Foster graph with $\iota(\Gamma)=\{3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3\}$.
\end{remark}

\subsection*{Acknowledgements}
The author would like to thank Professor Eiichi Bannai and Professor Jack Koolen for their valuable comments. Also the author would like to thank the anonymous referees for their comments.


\begin{thebibliography}{10}

\bibitem{biggs}
N.~L.~Biggs.  \newblock {\em Algebraic Graph Theory}. \newblock second edition, Cambridge University Press, Cambridge, 1993.

\bibitem{bcn} A.~E.~Brouwer,~A.~M.~Cohen, and A.~Neumaier.  \newblock {\em Distance-Regular
Graphs}. \newblock Springer-Verlag, Berlin, 1989.

\bibitem{k=4} A.~E.~Brouwer and J.~H.~Koolen. \newblock The distance-regular graphs of valency four. \newblock {\em J. Algebraic Combin.}, 
10(1):5--24, 1999.

\bibitem{-1-b/2} J.~H.~Koolen.  \newblock The distance-regular graphs with
intersection number $a\sb 1\not=0$ and with an eigenvalue
$-1-(b\sb 1/2)$.  \newblock {\em Combinatorica}, 18(2):227--234, 1998.


\bibitem{k-y} J.~H.~Koolen and H.~Yu.  \newblock The distance-regular graphs such that all of its second largest local
eigenvalues are at most one.  \newblock {\em Linear Algebra Appl.}, 435(10):2507--2519, 2011.

\bibitem{ter-quadrangle} P.~Terwilliger.  \newblock Distance-regular graphs
with girth 3 or 4, I.  \newblock {\em J. Combin. Theory Ser.B}, 39(3):265--281, 1985.
\end{thebibliography}

\end{document}
