%% A LaTeX file for a 9 page document%%
\documentclass[12pt]{article}
\usepackage{latexsym}
\oddsidemargin .5cm
\evensidemargin .5cm
\textwidth=15.2truecm
\textheight=22.9truecm
\unitlength=1cm
\parskip=3pt
\baselineskip=15pt
\newtheorem{theo}{Theorem}[section]
\newtheorem{propo}[theo]{Proposition}
\newtheorem{lema}[theo]{Lemma}
\newtheorem{defi}[theo]{Definition}
\newtheorem{exemple}[theo]{Example}
\newtheorem{coro}[theo]{Corollary}
\newtheorem{guess}[theo]{Conjecture}
\def\proof{{\boldmath$\it Proof.$}\hskip 0.3truecm}
\def\endproof{\ \ \ $\Box$\vskip .2cm}
\newfont{\nset}{msbm10}
\newcommand{\ns}[1]{\mbox{\nset #1}}
\def\A{\mbox{\boldmath $A$}}
\def\e{\mbox{\boldmath $e$}}
\def\G{\Gamma}
\def\I{\mbox{\boldmath $I$}}
\def\J{\mbox{\boldmath $J$}}
\def\M{{\cal M}}
\def\R{\ns{R}}
\def\sp{\mathop{\rm sp}\nolimits}
\def\d{\partial}
\def\dgr{\mathop{\rm dgr}\nolimits}
\def\ecc{\mathop{\rm ecc}\nolimits}
\def\vec0{\mbox{\bf 0}}
\def\vecrho{\mbox{\boldmath $\rho$}}
\def\dist{\mathop{\rm dist}\nolimits}
\def\ev{\mathop{\rm ev}\nolimits}
\def\tr{\mathop{\rm tr}\nolimits}
\begin{document}
\title{A Quasi-Spectral Characterization \\
of Strongly Distance-Regular Graphs}
\author{M. A. Fiol
\\ {\small Departament de Matem\`atica Aplicada i Telem\`atica} \\
{\small Universitat Polit\`ecnica de Catalunya} \\
{\small Jordi Girona 1-3, M\`odul C3, Campus Nord } \\
{\small 08034 Barcelona, Spain; email: {\tt fiol@mat.upc.es}} }
\date{Submitted: April 30, 2000; Accepted: September 16, 2000. }
\maketitle
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics {\bf 7}
(2000),
\#R51\hfill}
\thispagestyle{empty}
\begin{abstract}
A graph $\G$ with diameter $d$ is strongly distance-regular if $\G$
is distance-regular and its distance-$d$ graph $\G_d$ is strongly
regular. The known examples are all the connected
strongly regular graphs (i.e. $d=2$), all the antipodal
distance-regular graphs, and some distance-regular graphs with
diameter $d=3$.
The main result in this paper is a
characterization of these graphs (among regular graphs with $d$
distinct eigenvalues), in terms of the eigenvalues, the sum of the
multiplicities corresponding to the eigenvalues with (non-zero)
even subindex, and the harmonic mean of the degrees of the
distance-$d$ graph.
\end{abstract}
{\bf AMS subject classifications.} 05C50
{\small 05E30 }
\section{Preliminaries}
Strongly distance-regular graphs were recently introduced by the
author \cite{f00} by combining the standard concepts of
distance-regularity and strong regularity. A {\it strongly
distance-regular graph\/} $\G$ is a distance-regular graph (of
diameter $d$, say) with the property that the distance-$d$ graph
$\G_d$---where two vertices are adjacent whenever they are at
distance $d$ in $\G$---is strongly regular. The only known
examples of these graphs are the strongly regular graphs (with
diameter
$d=2$), the antipodal distance-regular graphs, and the
distance-regular graphs with $d=3$ and third greatest eigenvalue
$\lambda_2=-1$. (In fact, it has been conjectured
that a strongly distance-regular graph is antipodal or has diameter
at most three.)
For these three families some spectral, or
``quasi-spectral", characterizations are known. Thus, it is
well-known that strongly regular graphs are characterized, among
regular connected graphs, as those having exactly three distinct
eigenvalues. In the other two cases, however, the spectrum
is not enough and some other
information about the graphs---such as the numbers of vertices at
maximum distance from each vertex---is needed to characterize
them. Then we speak about {\it quasi-spectral
characterizations\/}, as those in \cite{f97,fgy98} (for antipodal
distance-regular graphs) and \cite{vd98,f00} (for strongly
distance-regular graphs with diameter $d=3$). Quasi-spectral
characterizations for general distance-regular graphs were also
given in \cite{ha96,vdh97} (for diameter three) and \cite{fg96} (for
any diameter).
Following these works, we derive in
this paper a general quasi-spectral characterization of strongly
distance-regular graphs. This includes, as particular cases, most
of the previous results about such graphs, and allows us also to
obtain some new results about their spectra. In particular, our
approach makes clear some symmetry properties enjoyed by their
eigenvalues and multiplicities. Eventually, and after looking at the
expressions obtained, one gets the intuitive impression that
strongly distance-regular graphs are among the graphs
with more hidden ``spectral symmetries".
Before proceeding to our study we devote the rest of this
introductory section to fixing the
terminology and to recalling some basic results. Let
$\G$ a (simple, finite, and connected) graph with adjacency matrix
$\A:=\A(\G)$ and (set of) eigenvalues
$\ev
\G:=\{\lambda_0>\lambda_1>\cdots>\lambda_d\}$. The {\it
alternating polynomial\/}
$P$ of $\G$ is defined as the
(unique) polynomial of degree $d-1$ satisfying
$$
P (\lambda_0)=\max_{p\in \R_{d-1}[x]}\{p(\lambda_0):\,
\|p\|_\infty\le 1\}
$$
where $\|p\|_\infty=\max_{1\le i\le d}|p(\lambda_i)|$. It is known
that $P$ is characterized by taking $d$ alternating values $\pm 1$
at
$\ev \G$: $P(\lambda_{i})=(-1)^{i+1}$,
$1\le i\le d$, which, together with Lagrange interpolation, yields
\begin{equation}
\label{P(lambda)}
P(\lambda_0)=\sum_{i=1}^d \frac{\pi_0}{\pi_i}.
\end{equation}
where the $\pi_i's$ are moment-like parameters defined from the
eigenvalues as
$\pi_i:=\prod_{j=0,j\neq i}^
d|\lambda_i-\lambda_j|$, $0\le i\le d$,
and satisfying
\begin{equation}
\label{Pil}
\sum_{i\mbox{ {\scriptsize even} }} \frac{\lambda_i^l}{\pi_i}
=\sum_{i\mbox{ {\scriptsize odd} }}
\frac{\lambda_i^l}{\pi_i} \qquad (0\le l< d).
\end{equation}
(See \cite{fgy96a,fgy98} for more details.)
In this work, it is useful to consider the following
characterization of distance-regular graphs (see e.g. Biggs
\cite{b93} or Brouwer et al. \cite{bcn89}): A (connected) graph
$\G$, with vertex set $V=\{u,v,\ldots\}$, adjacency matrix
$\A$, and diameter $d$, is distance-regular if and only if there
exists a sequence of polynomials $p_0,p_1,\ldots,p_d$, called
the {\it distance polynomials\/}, such that $\dgr p_i=i$, $0\le i\le
d$, and
$$
\A_i:=\A(\G_i)=p_i(\A)\qquad (0\le i\le d),
$$
where $\A_i$ is the adjacency matrix of the distance-$i$ graph
$\G_i$ and, so, it is called the {\it distance-$i$ matrix\/} of $\G$.
Let $n:=|V|$ and assume that $\G$ has
spectrum $\sp
\G:=\{\lambda_0^{m(\lambda_0)},\lambda_1^{m(\lambda_1)},\ldots,
\lambda_d^{m(\lambda_d)}\}$ (as $\G$ is connected,
$m(\lambda_0)=1$). Then the distance polynomials are
orthogonal with respect to the scalar product
\begin{equation}
\label{scalar}
\langle p,q\rangle_{\G}:=\frac{1}{n}\tr (p(\A)q(\A))=\sum_{i=0}^d
\frac{m(\lambda_i)}{n} p(\lambda_i) q(\lambda_i),
\end{equation}
and they are normalized in such a way that
$\|p_i\|^2_\G =p_i(\lambda_0)$,
$0\le i\le d$. (Of course, this inner product makes sense---and it
will be used later---for any graph $\G$.) Moreover, if $\G_i(u)$
denotes the set of vertices at distance $i$ from a given vertex
$u$, we have
$p_i(\lambda_0)=n_i(u):=|\G_i(u)|$ for any $u\in V$ and $0\le i\le
d$. In fact, there are explicit formulas
giving the values of the highest degree polynomial $p_d$ at $\ev
\G$, in terms of the eigenvalues and their multiplicities. Namely,
\begin{equation}
\label{val-pd-mul}
p_d(\lambda_0)=n\left(\sum_{i=0}^{d}\frac{\pi_0^2}{m(\lambda_i)
\pi_i^2}
\right)^{-1};
\qquad
p_d(\lambda_i)=(-1)^i\frac{\pi_0 p_d(\lambda_0)}{\pi_i
m(\lambda_i)}.
\end{equation}
(From the second expression one has the known formulas
for the multiplicities in terms of $p_d$---see, e.g., Bannai and Ito
\cite{bi84}.) Hence, since
$p_d(\lambda_0)$ (the degree of
$\G_d$) is a positive integer, the polynomial $p_d$ must take
alternating values at the mesh $\ev\G$:
\begin{equation}
\label{sign-pd}
p_d(\lambda_i)>0\ \ \ (i \mbox{\rm \ even}); \qquad
p_d(\lambda_i)<0 \ \ \ (i \mbox{\rm \ odd}).
\end{equation}
In this paper, we also use the following
results about strongly regular graphs (see, for
instance, Cameron's survey \cite{c78} or Godsil's textbook
\cite{g93}):
\begin{lema}
\label{charac-srg}
(a) A graph $\G$, not complete or empty, with adjacency matrix
$\A$ is $(n,k;a,c)$-strongly regular if and only if
\begin{equation}
\label{charac-1-srg}
\A^2-(a-c)\A+(c-k)\I=\J,
\end{equation}
where $\J$ represents the all-$1$ matrix.
(b) A connected regular graph $\G$ with exactly three distinct
eigenvalues $\mu_0>\mu_1>\mu_2$ is a $(n,k;a,c)$-strongly regular
graph with parameters satisfying
\begin{equation}
\label{k-a-c}
k=\mu_0,\quad c-k=\mu_1\mu_2,\quad a-c=\mu_1+\mu_2.
\end{equation}
\end{lema}
Notice that, from the above and $\tr \A=0$, it follows that
$\mu_2<0$ and $\mu_1\ge 0$ (with $\mu_1= 0$ only when
$\G$ is the regular multipartite graph).
\section{A quasi-spectral characterization}
In this section we derive our main result, which characterizes
strongly-regular graphs among regular graphs, and study some of
its consequences.
Given any vertex $u$ of a graph with diameter $d$, we denote
by $N_i(u)$, $0\le i\le d$, the {\it $i$-neighbourhood\/} of $u$, or
set of vertices at distance at most $i$ from $u$.
Using some results from \cite{fg96,fgy96b}, the author proved in
\cite{f99} the following result, which is basic to our study.
\begin{theo}
\label{basic-result}
Let $\G$ be a regular graph with $n$ vertices and $d+1$ distinct
eigenvalues. For every vertex
$u\in V$, let
$s_{d-1}(u):=|N_{d-1}(u)|$. Then, any polynomial $R\in\R_{d-1}[x]$
satisfies the bound
\begin{equation}
\frac{R(\lambda_0)^2}{\|R\|_\G^2}\le \frac{n}
{\sum_{u\in V}\frac{1}{s_{d-1}(u)}},
\end{equation}
and equality is attained if and only if $\G$ is a distance-regular
graph. Moreover, in this case, we have
$
\frac{R(\lambda_0)}{\|R\|_\G^2}R=q_{d-1}:=\sum_{i=0}^{d-1} p_i
$,
where the $p_i$'s are the distance polynomials of $\G$.
\end{theo}
Note that the above upper bound is, in fact, the harmonic mean of
the numbers $s_{d-1}(u)$, $u\in V$, which is hereafter denoted
by
$H$. Moreover,
in case of equality, $q_{d-1}(\A)=\sum_{i=0}^{d-1}
\A_i=\J-\A_d$, and the distance-$d$ polynomial of $\G$ is just
\begin{equation}
\label{pd}
p_d=q_d-q_{d-1}=q_d-\frac{R(\lambda_0)}{\|R\|_\G^2}R
\end{equation}
where $q_d$ represents the {\it Hoffman
polynomial\/}; that is, $q_d=\frac{n}{\pi_0}\prod_{i=1}^d
(x-\lambda_i)$.
At this point it is useful to
introduce the following notation: For a graph with $n$ vertices,
spectrum $\{\lambda_0^{m(\lambda_0)},\ldots,
\lambda_d^{m(\lambda_d)}\}$, and alternating polynomial $P$, note
that, by (\ref{P(lambda)}), the value of
$P(\lambda_0)+1$ is given by the sum
\begin{equation}
\label{sym-S}
\Sigma:=\sum_{i=0}^{d}\frac{\pi_0}{\pi_i}=
1+\Sigma_e+\Sigma_o\, ,
\end{equation}
where $\Sigma_e$ (respectively $\Sigma_o$) denotes the sum of
the terms
$\pi_0/\pi_i$ with even non-zero (respectively, odd) index $i$. Note
also that, by (\ref{Pil}) with $l=0$, both numbers are closely
related: $\Sigma_o=\Sigma_e+1$. However,
the use of both symbols will reveal the symmetries of the
expressions obtained. With the same aim, let us also consider the
following sum decomposition:
\begin{equation}
\label{sym-s}
n = \sum_{i=0}^d m(\lambda_i)= 1+ \sigma_e + \sigma_o\, ,
\end{equation}
where $\sigma_e$ represents the sum of all
multiplicities of the eigenvalues with non-zero even subindex
$\sigma_e:=m(\lambda_2)+m(\lambda_4)+\cdots$, and
$\sigma_o:=n-\sigma_e-1=m(\lambda_1)+m(\lambda_3)+\cdots$
The following result generalizes for any diameter a theorem of the
author
\cite{f00} (the case of diameter three).
\begin{theo}
\label{main-result}
A regular graph $\G$, with $n$ vertices, eigenvalues
$\lambda_0>\lambda_1>\cdots>\lambda_d$, and parameters
$\sigma_e$, $\Sigma_e$ as above,
is strongly distance-regular if and only if the harmonic
mean of the numbers $s_{d-1}(u)$, $u\in V$, is
\begin{equation}
\label{num-charac-H}
H
=n-\frac{n\sigma_e\sigma_o}
{n\Sigma_e\Sigma_o+(\sigma_e-\Sigma_e)(\sigma_o+\Sigma_o)}.
\end{equation}
Moreover, if this is the case, $\G_d$ is a strongly regular graph
with degree $k=n-H$ and parameters
\begin{equation}
\label{c-a}
c =
k-k^2\frac{\Sigma_e\Sigma_o}{\sigma_e\sigma_o};\qquad
a=
c+k\left(\frac{\Sigma_e}{\sigma_e}
-\frac{\Sigma_o}{\sigma_o}\right).
\end{equation}
\end{theo}
\proof
Given any real number $t$, let us consider the
polynomial $R:=(1+\frac{t}{2})P-\frac{t}{2}$, where $P$
is the alternating polynomial of $\G$. Notice that, from the
properties of $P$, we have
$R(\lambda_i)=1$ for any odd $i$, $1\le i\le d$, and
$R(\lambda_i)=-1-t$ for every even $i\neq 0$. Then, the square
norm of $R$ satisfies
\begin{equation}
\label{N}
n\|R\|_\G^2 = R^2(\lambda_0) +\sum_{i=1}^d
R^2(\lambda_i)m(\lambda_i)
=R^2(\lambda_0) +\sigma_e(1+t)^2+\sigma_o.
\end{equation}
Hence, by Theorem \ref{basic-result}, we must have, for
any $t$,
\begin{equation}
\label{bound}
\Psi(t)
:=\frac{n\left[(1+\frac{t}{2})P(\lambda_0)-\frac{t}{2}\right]^2}
{\left[(1+\frac{t}{2})P(\lambda_0)-\frac{t}{2}\right]^2
+\sigma_e(1+t)^2+\sigma_o}
=\frac{R(\lambda_0)^2}{\|R\|_\G^2} \le H.
\end{equation}
Since we are interested in the case of equality,
we must find the maximum of the function $\Psi$.
Such a maximum is attained at
\begin{equation}
\label{t0}
t_0=\frac{ \sigma_o}{\sigma_e}
\frac{ P(\lambda_0) - 1}{P(\lambda_0)+1}-1
\end{equation}
and its value is
\begin{eqnarray}
\label{Psi-max-PP}
\Psi_{\max}:=\Psi(t_0)
& = & n-\frac{4n\sigma_e\sigma_o} {(n-1)\Sigma^2+4\sigma_o
(\sigma_e-\Sigma)} \\
& = & n-\frac{n\sigma_e\sigma_o}
{n\Sigma_e\Sigma_o+(\sigma_e-\Sigma_e)(\sigma_o+\Sigma_o)},
\label{Psi-max}
\end{eqnarray}
where we have used (\ref{sym-S}) and
(\ref{sym-s}). Consequently,
$\Psi_{\max}\le H$ and, from the same theorem, the equality case
occurs if and only if
$\G$ is a distance-regular graph with distance $d$-polynomial
given by (\ref{pd}). From this fact, let us now see that
$\G_d$ is strongly regular. In our case, all
inequalities in (\ref{bound}) and (\ref{N}) become equalities with
$t=t_0$ given by (\ref{t0}), so giving
$$
\textstyle
R(\lambda_0) =
\left(1+\frac{t_0}{2}\right)P(\lambda_0)-\frac{t_0}{2};
\qquad
\|R\|_\G^2 = R^2(\lambda_0)
+\sigma_e(1+t_0)^2+\sigma_o.
$$
This allows us to compute, through (\ref{pd}), the distance-$d$
polynomial and its relevant values:
\begin{eqnarray*}
\mu_0 & := & p_d(\lambda_0) = n- H; \\
\mu_1 & := &
p_d(\lambda_i)=-\frac{R(\lambda_0)}{\|R\|_\G^2}R(\lambda_i)
=\frac{R(\lambda_0)}{\|R\|_\G^2}(1+t_0)
\qquad (\mbox{even $i\neq 0$}); \\
\mu_2 & := &
p_d(\lambda_i)=-\frac{R(\lambda_0)}{\|R\|_\G^2}R(\lambda_i)
=-\frac{R(\lambda_0)}{\|R\|_\G^2}
\qquad (\mbox{odd $i$}).
\end{eqnarray*}
Then $\G_d$ is a regular graph with degree $k=\mu_0$ and has
at most three eigenvalues
$\mu_0\ge
\mu_1> \mu_2$ (with multiplicities $m(\mu_0)=1$,
$m(\mu_1)=\sigma_e$, and $m(\mu_2)=\sigma_o$). If it has
exactly three eigenvalues,
$\mu_0>\mu_1$, then $\G_d$ must be connected
and Lemma \ref{charac-srg} applies. Otherwise, if
$\mu_0=\mu_1$, the graph
$\G_d$ is simply constituted by disjoint copies of the complete
graph on $k+1$ vertices. (See
\cite{f00} for more details.) In both cases $\G_d$ is strongly
regular, as claimed.
Moreover, after some algebraic manipulations,
the above formulas yield
\begin{eqnarray}
\label{k}
k & = & \frac{n\sigma_e\sigma_o}
{n\Sigma_e\Sigma_o+(\sigma_e-\Sigma_e)(\sigma_o+\Sigma_o)};
\\
\label{mu1}
\mu_1 & = & \frac{n\Sigma_e\sigma_o}
{n\Sigma_e\Sigma_o+(\sigma_e-\Sigma_e)(\sigma_o+\Sigma_o)}
=k\frac{ \Sigma_e}{\sigma_e};
\\
\label{mu2}
\mu_2 & = & \frac{-n\sigma_e\Sigma_o}
{n\Sigma_e\Sigma_o+(\sigma_e-\Sigma_e)(\sigma_o+\Sigma_o)}
=-k\frac{\Sigma_o}{\sigma_o};
\end{eqnarray}
and the values of $c$ and $a$ follow from (\ref{k-a-c}).
Conversely, if $\G$ is a strongly distance-regular graph,
its distance-$d$ graph $\G_d$,
with adjacency matrix $p_d(\A)$, is a strongly regular graph
with either three or two eigenvalues, $\mu_0\ge \mu_1
>\mu_2$, satisfying
$\mu_0=p_d(\lambda_0)=n_d(u):=|\G_d(u)|$ for every $u\in V$,
$\mu_1=p_d(\lambda_i)\ge 0$ for every even
$i\neq 0$, and $\mu_2=p_d(\lambda_i)$ for every odd $i$. Thus, by
adding up the corresponding multiplicities, obtained from the
second expression in (\ref{val-pd-mul}), we get
$$
\sigma_e=\sum_{ i \mbox{ {\scriptsize even} } (i\neq
0)}\frac{\pi_0}{\pi_i}
\frac{\mu_0}{\mu_1}=\frac{\mu_0}{\mu_1}\Sigma_e\, ;
\qquad
\sigma_o=-\sum_{ i\mbox{ {\scriptsize odd} }}\frac{\pi_0}{\pi_i}
\frac{\mu_0}{\mu_2}=-\frac{\mu_0}{\mu_2}\Sigma_o\, .
$$
These two equations give the values
of $\mu_1$ and $\mu_2$---compare with (\ref{mu1}) and
(\ref{mu2})---which, substituted into
$$
n\|p_d\|_\G^2=\mu_0^2+\sigma_e\mu_1^2+\sigma_o\mu_2^2
=n\mu_0,
$$
and solving for $\mu_0=n_d(u)$, give
\begin{equation}
\label{nd}
n_d(u)
=\frac{n\sigma_e\sigma_o}
{n\Sigma_e\Sigma_o+(\sigma_e-\Sigma_e)(\sigma_o+\Sigma_o)}
\end{equation}
for every vertex $u\in V$. Hence, all the numbers
$s_{d-1}(u)=n-n_d(u)$, $u\in V$, are the same and their harmonic
mean $H$ satisfies (\ref{num-charac-H}). This completes the
proof of the theorem.
\endproof
{}From the above proof, notice that, alternatively,
we can assert that the regular graph $\G$ is
strongly distance-regular if and only if the distance-$d$ graph
$\G_d$ is $k$-regular with degree
$k=n_{d}(u)$ given by (\ref{k}) or (\ref{nd}).
As a by-product of such a proof, we can also give
bounds for the sum of ``even multiplicities" $\sigma_e$ in any
regular graph, in terms of its eigenvalues and harmonic mean~$H$.
\begin{coro}
Let $\G$ be a regular graph , with $n$ vertices,
eigenvalues
$\lambda_0>\lambda_1>\cdots>\lambda_d$, and harmonic
mean $H$. Set $\alpha:=\frac{n}{2}(1-\frac{1}{H})$ and
$\beta:=\Sigma_e(\frac{n}{H}-1)$. Then the sum $\sigma_e$ of even
multiplicities satisfies the bounds
$$
\alpha-\beta-\sqrt{\alpha(1-\alpha\beta\Sigma)}
\le \sigma_e
\le \alpha-\beta+\sqrt{\alpha(1-\alpha\beta\Sigma)}.
$$
\end{coro}
\proof
Solve for $\sigma_e$ the inequality
$$
n-\Psi_{\max}
=\frac{4n\sigma_e(n-\sigma_e-1)}
{(n-1)\Sigma^2+4(n-\sigma_e-1) (\sigma_e-\Sigma)}\ge n-H,
$$
which comes from (\ref{Psi-max-PP}), (\ref{sym-s}), and
$\Psi_{\max}\le H$, and use (\ref{sym-S}).
\endproof
Let us now consider some particular cases of the above theorem,
which contain some previous results of Van Dam, Garriga, and the
author. Note first that, for some particular cases, we do not need
to know the multiplicity sum $\sigma_e$ (and hence nor
$\sigma_o$), since it can be deduced from the eigenvalues. For
instance, for diameter $d=3$, the multiplicities
$m_1,m_2,m_3$ of a regular graph must satisfy the system
$$
\begin{array}{ccccc}
1+m_1+m_2+m_3 & = & n \\
\lambda_0+m_1\lambda_1+m_2\lambda_2+m_3\lambda_3
& = & 0 \\
\lambda_0^2+m_1\lambda_1^2+m_2\lambda_2^2+m_3 \lambda_3^2
& = & n\lambda_0
\end{array}
$$
whence we get
\begin{equation}
\label{se(d=3)}
\sigma_e=m_2=
\frac{\pi_0-n(\lambda_1\lambda_3+\lambda_0)
(\lambda_0-\lambda_2)}{\pi_2}.
\end{equation}
Thus, Theorem \ref{main-result} gives the following result.
\begin{coro}
A connected $\delta$-regular graph $\G$ with $n$ vertices and
eigenvalues
\linebreak
$\lambda_0(=\delta)>\lambda_1>\lambda_2>\lambda_3$ is
strongly distance-regular if and only if the harmonic mean of the
numbers $s_2(u)=1+\delta+n_2(u)$, $u\in V$, satisfies
\begin{equation}
\label{main-theo}
H=n-\frac{4n\sigma_o\sigma_e}
{(n-1)\Sigma^2+4\sigma_o (\sigma_e+1-\Sigma)},
\end{equation}
where $\sigma_e$ is given by (\ref{se(d=3)}),
$\sigma_o=n-\sigma_e-1$ and
$\Sigma=\sum_{i=0}^3 (\pi_0/\pi_i)$. \endproof
\end{coro}
The above result
slightly improves a similar characterization given in \cite{f00}, in
terms of the degree of the graph $\G_3$, and where the
additional condition $\lambda_2=-1$ was required.
Let us now consider the case $a=c$. In this case, an strongly
regular graph satisfying this condition is also called an
$(n,k,c)$-graph (see Cameron
\cite{c78}) and, consequently, we will speak about an
$(n,k,c)$-strongly distance-regular graph.
\begin{coro}
\label{charac-s-d-r-1}
Let $\G$ be a regular graph with eigenvalues
$\lambda_0>\lambda_1>\cdots>\lambda_d$ and alternating
polynomial
$P$. Then $\G$ is an
$(n,k,c)$-strongly distance-regular graph if and only if any of the
following conditions hold.
(a) The harmonic mean $H$ of the numbers $s_{d-1}(u)$, $u\in V$, is
\begin{equation}
\label{num-charac-H(a=c)}
H=\frac{nP(\lambda_0)} {P(\lambda_0)^2+n-1}.
\end{equation}
(b) The distance-$d$ graph $\G_d$
is $k$-regular with degree
\begin{equation}
\label{num-charac-k(a=c)}
k=\frac{n(n-1)}{P(\lambda_0)^2+n-1}.
\end{equation}
In such a case, the other parameters of $\G_d$ are
$(a=)c=k(k-1)/(n-1)$.
\end{coro}
\proof
We only prove sufficiency for condition (a), the other
reasonings being almost straightforward from previous
material. Note that the right-hand expression in
(\ref{num-charac-H(a=c)}) corresponds to the value of the function
$\Psi$ at $t=0$ satisfying
$$
\Psi(0)\le \Psi(t_0)=\Psi_{\max} \le H.
$$
Then, if equality (\ref{num-charac-H(a=c)}) holds, it must be
$t_0=0$,
$\Psi_{\max} = H$ and, by Theorem \ref{main-result}, $\G$ is
strongly distance-regular. Moreover, for such a value of
$t_0$, and using that $P(\lambda_0)=2\Sigma_e+1=2\Sigma_o-1$
and $\sigma_o=n-\sigma_e-1$, Eq.~(\ref{t0}) yields
$$
\frac{\sigma_o}{\sigma_e}
\frac{P(\lambda_0) - 1}{P(\lambda_0)+1}
=\frac{\sigma_o}{\sigma_e}
\frac{\Sigma_e}{\Sigma_o}=1
\quad\Rightarrow\quad
\frac{\Sigma_e}{\sigma_e}=\frac{\Sigma_o}{\sigma_o}
\quad\mbox{and}\quad
\sigma_e
=\frac{(n-1)(P(\lambda_0)-1)}{2P(\lambda_0)}
$$
whence (\ref{c-a}) gives
$$
a=c=k-k^2\frac{\Sigma_e^2}{\sigma_e^2}
=k-k^2\frac{P(\lambda_0)^2}{(n-1)^2}
=\frac{k(k-1)}{n-1}
$$
(where we have used that
$P(\lambda_0)^2=(\frac{n}{k-1}-1)(n-1)$), as claimed.
\endproof
Notice that, as before, the characterization in (a)
implies that of (b). The latter was given in
\cite{vd98} for diameter $d=3$, whereas the general case was
solved in \cite{fg3}.
Let us now consider the antipodal case. Note that a
distance-regular graph $\G$ is an
antipodal $r$-cover if and only if its distance-$d$
graph $\G_d$ is constituted by disjoint copies of the complete
graph $K_r$, which can be seen as a (unconnected)
$(n,r-1;r-2,0)$-strongly regular graph.
\begin{coro}
\label{charac-antipod}
Let $\G$ be a regular graph with $n$ vertices,
eigenvalues $\lambda_0>\lambda_1>\cdots>\lambda_d$,
$\Sigma=
\sum_{i=0}^d(\pi_0/\pi_i)$, and
sum of even multiplicities $\sigma_e$. Then
$\G$ is an $r$-antipodal distance-regular graph if and only if
$\sigma_e=\Sigma_e$ and the harmonic mean of the numbers
$s_{d-1}(u)$, $u\in V$, is
\begin{equation}
\label{charac-antipodal}
H=n\left(1-\frac{2}{\Sigma}\right) -1.
\end{equation}
In this case, $r=2n/\Sigma$.
\end{coro}
\proof
Again we only prove sufficiency. Let
$\Sigma=P(\lambda_0)+1$. With
$\sigma_e=\Sigma_e$, Eq.~(\ref{Psi-max}) particularizes to
$$
\Psi_{\max}=n-\frac{\sigma_o}{\Sigma_o}
=n-\frac{n-\Sigma_e-1}{\Sigma_o}
=n-\frac{2n}{\Sigma}-1,
$$
where we have used that $\Sigma_o=\Sigma_e+1=\Sigma/2$.
Hence, by Theorem \ref{main-result}, $\G$ is
strongly distance-regular, with $\G_d$ having degree
$k=(2n/\Sigma)-1$. Finally, the antipodal character comes from
(\ref{c-a}), giving $c=0$ and
$a=k-1$, so that $r=k+1=2n/\Sigma$.
\endproof
A similar result in terms of $r$
can be found in \cite{f97} without using the condition
on the multiplicity sum $\sigma_e=\Sigma_e$.
\begin{thebibliography}{99}
\bibitem{bi84}
E. Bannai and T. Ito, {\it Algebraic Combinatorics I: Association
Schemes.} Benjamin/Cummings, Menlo Park, CA, 1984.
\bibitem{b93}
N. Biggs, {\it Algebraic Graph Theory.} Cambridge University Press,
Cambridge, 1974; second edition: 1993.
\bibitem{bcn89}
A.E. Brouwer, A.M. Cohen, and A. Neumaier, {\it Distance-Regular
Graphs.} Springer-Verlag, Berlin, 1989.
\bibitem{c78}
P.J. Cameron, Strongly regular graphs, {\it in: Selected Topics in
Graph Theory}, edited by L.J. Beineke and R.J. Wilson. Academic
Press, New York, 1978, 337--360.
\bibitem{vd98}
E.R. van Dam, Bounds on special subsets in graphs, eigenvalues and
association schemes, {\it J. Algebraic Combin.} {\bf 7} (1998),
no. 3, 321--332.
\bibitem{vdh97}
E.R. van Dam and W.H. Haemers, A characterization of
distance-regular graphs with diameter three, {\it J. Algebraic
Combin.} {\bf 6} (1997), no. 3, 299--303.
\bibitem{f97}
M.A. Fiol,
An eigenvalue characterization of antipodal distance-regular
graphs. {\it Electron. J. Combin.} {\bf 4} (1997), no. 1, \#R30.
\bibitem{f99}
M.A. Fiol,
Algebraic characterizations of distance-regular graphs,
{\it Discrete Math. (Proc. 11th Inter. Conf. on Formal Power
Series and Algebraic Combinatorics, Barcelona, 7-11 June 1999)},
to appear.
\bibitem{f00}
M.A. Fiol,
Some spectral characterizations
of strongly distance-regular graphs.
{\it Combin. Probab. Comput.}, to appear.
\bibitem{fg96}
M.A. Fiol and E. Garriga,
{}From local adjacency polynomials to locally
pseudo-distance-regular graphs, {\it J. Combin. Theory Ser. B}
{\bf 71} (1996), 162--183.
\bibitem{fg3}
M.A. Fiol and E. Garriga,
Pseudo-strong regularity around a set, submitted.
\bibitem{fgy96a}
M.A. Fiol, E. Garriga, and J.L.A. Yebra, On a class
of polynomials and its relation with the spectra and diameters of
graphs, {\it J. Combin. Theory Ser. B} {\bf 67} (1996), 48--61.
\bibitem{fgy96b}
M.A. Fiol, E. Garriga and J.L.A. Yebra,
Locally pseudo-distance-regular graphs,
{\it J. Combin. Theory Ser.~B} {\bf 68} (1996), 179--205.
\bibitem{fgy98}
M.A. Fiol, E. Garriga, and J.L.A. Yebra, From regular boundary graphs
to antipodal distance-regular graphs, {\it J. Graph Theory} {\bf 27}
(1998), no. 3, 123--140.
\bibitem{g93}
C.D. Godsil, {\it Algebraic Combinatorics.} Chapman and Hall,
London/New York, 1993.
\bibitem{ha96}
W.H. Haemers, Distance-regularity and the spectrum of graphs,
{\it Linear Algebra Appl.} {\bf 236} (1996), 265--278.
\end{thebibliography}
\end{document}