% 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\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{m3$ 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) $-10$. 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} 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 |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) -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(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}