%% A LaTeX209 file for a 11 page document%% \documentstyle[12pt]{article} \oddsidemargin .5cm \evensidemargin .5cm \textwidth=15.2truecm \textheight=20truecm \unitlength=1cm \parskip=3pt \baselineskip=15pt \newtheorem{theo}{Theorem}[section] \newtheorem{propo}[theo]{Proposition} \newtheorem{lema}[theo]{Lemma} \newtheorem{defi}[theo]{Definition} \newtheorem{example}[theo]{Example} \newtheorem{coro}[theo]{Corollary} \newtheorem{guess}[theo]{Conjecture} \def\proof{{$\boldmath Proof.$}\hskip 0.3truecm} \def\endproof{\ \ $\Box$\vskip .2cm} \input amssym.def \newsymbol\rtimes 226F \newfont{\nset}{msbm10} \newcommand{\ns}[1]{\mbox{\nset #1}} \def\A{\mbox{\boldmath $A$}} \def\B{\mbox{\boldmath $B$}} \def\Bo{{\cal B}} \def\C{\mbox{\boldmath $C$}} \def\D{\mbox{\boldmath $D$}} \def\E{\mbox{\boldmath $E$}} \def\G{\Gamma} \def\I{\mbox{\boldmath $I$}} \def\J{\mbox{\boldmath $J$}} \def\K{\mbox{\boldmath $K$}} \def\M{{\cal M}} \def\O{\mbox{\boldmath $O$}} \def\R{\ns{R}} \def\Z{\ns{Z}} \def\d{\partial} \def\dist{\mathop{\rm dist}\nolimits} \def\ecc{\mathop{\rm ecc}\nolimits} \def\exc{\mathop{\rm exc}\nolimits} \def\e{\mbox{\boldmath $e$}} \def\f{\mbox{\boldmath $f$}} \def\j{\mbox{\boldmath $j$}} \def\u{{\mbox {\boldmath $u$}}} \def\v{{\mbox {\boldmath $v$}}} \def\w{{\mbox {\boldmath $w$}}} \def\x{\mbox{\boldmath $x$}} \def\z{\mbox{\boldmath $z$}} \def\vecphi{\mbox{\boldmath $\phi$}} \def\vecnu{\mbox{\boldmath $\nu$}} \def\vecrho{\mbox{\boldmath $\rho$}} \def\vec0{\mbox{\bf 0}} \def\ev{\mathop{\rm ev}\nolimits} \def\Ker{\mathop{\rm Ker}\nolimits} \def\Spec{\mathop{\rm sp}\nolimits} \def\tr{\mathop{\rm tr}\nolimits} \begin{document} \title{An Eigenvalue Characterization \\ of Antipodal 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: July 19, 1997; Accepted: November 14, 1997.} \maketitle \pagestyle{myheadings} \markright{\sc the electronic journal of combinatorics 4 (1997), \#R30\hfill} \thispagestyle{empty} \begin{abstract} Let $\G$ be a regular (connected) graph with $n$ vertices and $d+1$ distinct eigenvalues. As a main result, it is shown that $\G$ is an $r$-antipodal distance-regular graph if and only if the distance graph $\G_d$ is constituted by disjoint copies of the complete graph $K_r$, with $r$ satisfying an expression in terms of $n$ and the distinct eigenvalues. \end{abstract} {\bf AMS subject classifications.} 05C50 {\small 05E30 } \section{Introduction} The core of spectral graph theory is to describe the properties of a graph by its spectrum and find conditions that cospectral graphs may not share. For instance, consider the following question: Can we see from the spectrum of a graph with diameter $D$, say, whether it is distance-regular? Since a long time it was known that the answer to this question is `yes' when $D\le 2$ and `not' if $D\ge 4$. Then, on the basis of these results, it had been conjectured (cf. Cvetkovi\'c, Doob, and H. Sachs \cite{cds}) that the answer is also `yes' for $D=3$, but recently Haemers \cite{ha96} disproved the conjecture constructing some counterexamples. So, in general the spectrum is not sufficient to assure distance-regularity and, if we want to go further, we must require the graph to satisfy some additional conditions. In this direction, Van Dam and Haemers \cite{vdh96} showed that, in the case $D=3$, such a condition could be the number $n_d$ of vertices at ``extremal distance" $D=d$ (where $d+1$ is the number of distinct eigenvalues) from each vertex. Independently, Garriga, Yebra and the author \cite{fgy2} settled the case $n_d=1$ (for any value of $D$), that is the case of 2-antipodal distance-regular graphs. Finally, Garriga and the author \cite{fg2} solved the general case, characterizing distance-regular graphs as those regular graphs whose number of vertices at distance $d$ from each vertex is what it should be (a number that depends only on the spectrum of the graph.) An striking peculiarity of the case $n_d=1$ ($2$-antipodal graphs) is that, in fact, we do not need to look at the whole spectrum, but only at the distinct eigenvalues (its multiplicities can be deduced from them.) The main contribution of this paper is to show that this is also true for $r$-antipodal distance-regular graphs. As a main result it is shown that an antipodal regular graph is distance-regular if, and only if, its `fibres' (that is, the sets of antipodal vertices) have all cardinality $r$, a number depending on the order and the eigenvalues of the graph. This result is obtained via an spectral bound for the $k$-independence number, or (standard) independence number of the $k$-th power of the graph, and the study of the limit case in which such a bound is attained. Let us now fix the terminology and notation used throughout the paper. Thus, $\G =(V,E)$ denotes a connected (simple and finite) graph with {\it order} $n:=|V|$ and adjacency matrix $\A=\A(\G)$. The {\it distance} between two vertices $u,v\in V$ is represented by $\dist (u,v)$. The {\it eccentricity} of a vertex $u$ is $\ecc(u) :=\max_{v\in V}\dist (u,v)$, and the {\it diameter} of $\G$ is $D :=\max_{u\in V}\ecc (u)$. As usual, $\G_k(u)$, $0\le k\le \ecc (u)$, denotes the set of vertices at distance $k$ from $u$, and $\G_1(u)$ is simply written as $\G(u)$. The {\it distance-$k$ graph} $\G_k$, $0\le k\le D$, is the (possibly non-connected) graph on $V$ where two vertices are adjacent whenever they are at distance $k$ in $\G$. Thus, in particular, $\G_0$ is the trivial graph on $n$ vertices, and $\G_1=\G$. The adjacency matrix of $\G_k$, denoted by $\A_k$, is usually referred as the {\it distance-$k$ matrix} of $\G$. A graph $\G$ of diameter $D$ is called {\it antipodal} if, for any given vertex $u\in V$, the set $\{u\}\cup \G_D(u)$ consists of vertices which are mutually at distance $D$. In other words, there exists a partition of the vertex set into classes (called the {\it fibres} of $\G$) with the property that two distinct vertices are in the same class iff they are at distance $D$ (see, for instance, Godsil \cite{g93}.) If all the fibres have the same cardinality, say $r$, we say that $\G$ is an $r$-antipodal graph. We index all the involved matrices and vectors by the vertices of $\G$. Moreover, for any vertex $u\in V$, we denote by $\e_u$ the $u$-th unitary vector of the canonical basis of $\R^n$. Thus, the {\it characteristic vector} of a vertex set $U\subset V$ is just $\e_U:=\sum_{u\in U} \e_u$. As usual, the adjacency matrix $\A$ of $\G$ is seen as an endomorphism of $\R^n$. We let a polynomial $p\in\R_k[x]$ operate on $\R^n$ by the rule $p\w:=p(\A)\w$, where $\w\in \R^n$, and the matrix is not specified unless some confusion may arise. As usual, $\J$ denotes the $n\times n$ matrix with all entries equal to $1$, and similarly $\j \in \R^n$ is the all-$1$ vector. The {\it spectrum} of $\G$ is the set of eigenvalues of $\A$ together with their multiplicities: $$ \Spec \G := \{\lambda_0^{m_0},\lambda_1^{m_1},\ldots,\lambda_d^{m_d}\} $$ where the superscripts denote multiplicities. Recall that the largest positive eigenvalue $\lambda_0$ (with multiplicity one if $\G$ is connected) has an eigenvector $\vecnu=(\nu_1,\nu_2,\ldots,\nu_n)^\top$, which can be taken with all its entries positive, and we will consider it normalized in such a way that its smallest entry is $1$. Thus, $\vecnu=\j$ when $\G$ is regular. In some of our results we do not use the whole spectrum, but only the mesh (set) constituted by all the distinct eigenvalues, that is $$ \ev \G:=\{\lambda_0, \lambda_1,\ldots,\lambda_d \} $$ in decreasing order: $\lambda_0>\lambda_1>\cdots>\lambda_d$. (We follow here the notation of Godsil \cite{g93}.) Associated to such a mesh, we make ample use of the moment-like positive numbers $\pi_i$, which are defined as \begin{equation} \label{pi_i} \pi_i=\prod_{j=0, j\neq i}^d |\lambda_i-\lambda_j| \ \ \ (0\le i\le d). \end{equation} As it is well-known, if $\G$ is connected, its diameter is at most $ d=|\ev \G |-1$ (see, for instance, Biggs \cite{b93}.) Then, we say that $\G$ is extremal when it has ``spectrally maximum" diameter $D=d$. We also say that $\G$ is {\it diametral} when all its vertices have eccentricity equal to the diameter. In order to obtain bounds on the diameter of a graph in terms of its eigenvalues, Garriga, Yebra and the author \cite{fgy1} used the so-called {\it alternating polynomial} $P_k$, $0\le k\le d-1$, which is the (unique) polynomial satisfying $$ P_k (\lambda_0)=\max_{p\in \R_k[x]}\{p(\lambda_0):\, \|p\|_\infty\le 1\} $$ where $\|p\|_\infty=\max_{1\le i\le d}|p(\lambda_i)|$. When $k=d-1$, we simply speak about the {\it alternating polynomial}, $P:=P_{d-1}$. In \cite{fgy1} it was proved that the $k$-alternating polynomial is characterized by taking $k+1$ alternating values $\pm 1$ at $\ev \G$, with $P_k(\lambda_1)=1$ and $P_k(\lambda_d)=(-1)^k$. In particular, for $k=d-1$, this characterization gives $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} Some particular cases of these polynomials were also considered by Van Dam and Haemers in \cite{vdh95}. We finally recall that the {\it Kronecker product} of two matrices $\A=(a_{ij})$ and $\B$, denoted by $\A\otimes \B$, is obtained by replacing each entry $a_{ij}$ with the matrix $a_{ij}\B$, for all $i$ and $j$. Then, if $\u$ and $\v$ are eigenvectors of $\A$ and $\B$, with corresponding eigenvalues $\lambda$ and $\mu$, respectively, then $\u\otimes \v$ (seeing $\u$ and $\v$ as matrices) is an eigenvector of $\A\otimes \B$, with eigenvalue $\lambda\mu$. \section{The $k$-independence number} Let $\G=(V,E)$ be a graph with diameter $D$. A vertex set $U\subset V$ is said to be $k$-independent, for some integer $k\ge 0$, if their vertices are mutually at distance greater than $k$. By convention, $U=\{u\}$ will be supposed to be $k$-independent for every $k$. The {\it $k$-independence number} $\alpha_k$ of $\G$ is then defined as the cardinality of a maximum $k$-independent set. Thus, trivially, $\alpha_0=n$ and $\alpha_k=1$ if $k\ge D$. Moreover, $\alpha_1\equiv \alpha$ is the standard {\it independence} or {\it stability} number. Notice also that $\alpha_k$ is, in fact, the independence number of the $k$-th power of $\G$. In \cite{fg1}, Garriga and the author showed that, when $0\le k\le d-1$, the $k$-independence number of a regular graph satisfies the following spectral upperbound $$ \alpha_k < \frac{2 n}{P_k (\lambda_0)+1}+1. $$ where $P_k$ is the $k$-alternating polynomial of $\G$. This was derived as a consequence of a result on the {\it $(s,t)$-diameter}, which is the maximum distance between two subsets of $s$ ant $t$ vertices. Here we begin with a result which slightly improves this bound and, more important, tell us what happens when the bound is attained. Although both bounds are very similar, the method used here is quite different from that used in \cite{fg1}. Roughly speaking, we must now use a more precise technique, which, rather than the distance between two subsets, should take into account all the distances between vertices of a unique subset. As noted by the referee, the improved bound can also be derived by using `eigenvalue interlacing' (see Haemers' survey \cite{ha95} on this versatile technique.) More details about this approach can be found in \cite{f}. \begin{theo} \label{theo-k-indepen} Let $\G$ be a connected regular graph with $n$ vertices, mesh of eigenvalues $\ev \G=\{\lambda_0,\lambda_1,\ldots,\lambda_d\}$, and $k$-alternating polynomial $P_k$. Then, for any $0\le k\le d-1$, its $k$-independence number satisfies \begin{equation} \label{k-indepen} \alpha_k \le \frac{2 n}{P_k (\lambda_0)+1}. \end{equation} If equality holds for some (maximum) $k$-independent set $U$, then there exists a polynomial $p\in\R_{d}[x]$ (independent of $U$) such that \begin{equation} \label{vec-equality} p\e_u=\e_{U\setminus \{u\}}. \end{equation} for every vertex $u\in U$. \end{theo} \proof Let $U=\{u_0,u_1,\ldots,u_{r-1}\}$ be a maximum $k$-independent set, where $r=|U|=\alpha_k$. From the $k$-alternating polynomial $P_k$ of $\G$, we consider the polynomial $Q_k:=\frac{r}{2}P_k+\frac{r}{2}-1$. Then, since $P_k(\lambda_0)\ge 1$ and $-1\le P_k(\lambda_i)\le 1$ for $i\neq 0$, the matrix $Q_k(\A)$ has eigenvalues $Q_k(\lambda_0)\ge r-1$ and $Q_k(\lambda_i)$ satisfying $-1\le Q_k(\lambda_i)\le r-1$ for $1\le i\le d$. Now consider the matrix $\B:=\A(K_r)\otimes Q_k(\A)$. For instance, for $r=3$ we have $$ \B= \left( \renewcommand{\arraystretch}{1.8} \begin{array}{c|c|c} \O & Q_k(\A) & Q_k(\A) \\ \hline Q_k(\A) & \O & Q_k(\A) \\ \hline Q_k(\A) & Q_k(\A) & \O \end{array} \right). $$ The complete graph $K_r$ has eigenvalues $r-1$ and $-1$ (with multiplicity $r-1$), with corresponding orthogonal eigenvectors $\j\in \R^r$ and $\vecphi_i=(1,\omega^i,\omega^{2i},\ldots,\omega^{(r-1)i})^{\top}$, $1\le i\le r-1$, where $\omega$ is a primitive $r$-th root of $1$, say $\omega:=e^{j\frac{2\pi}{r}}$. Consequently, each eigenvector $\u$ of $Q_k(\A)$ with eigenvalue $Q_k(\lambda)$, $\lambda\in \ev\G$, gives rise to the eigenvalues $(r-1)Q_k(\lambda)$ and $-Q_k(\lambda)$ (with multiplicity $r-1$), with corresponding orthogonal eigenvectors $\u_0:=\j\otimes \u$ and $\u_i:=\vecphi_i\otimes \u$, $1\le i\le r-1$. Thus, when $\lambda\neq \lambda_0$, we have $-1\le Q_k(\lambda)\le r-1$ and hence the corresponding eigenvalues of $\B$ are within the interval $[-(r-1), (r-1)^2]$. Moreover, $\B$ has maximum eigenvalue $(r-1)Q_k(\lambda_0)\ge (r-1)^2$. Now take the vector $\f_U:=(\e_{u_0}^\top |\e_{u_1}^\top | \cdots | \e_{u_{r-1}}^\top )^\top\in \R^{rn}$, and consider its spectral decomposition: \begin{equation} \label{spectral-decomp} \f_U= \sum_{i=0}^{r-1}\frac{\langle \f_U, \j_i\rangle }{\|\j_i\|^2}\j_i+\z_U=\frac{1}{n}\j_0+\z_U \end{equation} where $\z_U\in \langle\j_0,\j_1,\ldots, \j_{r-1}\rangle ^{\bot}$, and we have used that $\langle \f_U, \j_0\rangle=r$, $\|\j_i\|^2=rn$, and $\langle \f_U, \j_i\rangle=\sum_{j=0}^{r-1}\omega^{ij}=0$, for any $1\le i\le r-1$. From (\ref{spectral-decomp}), we get $$ \|\z_U \|^2 =\|\f_U\|^2-\frac{1}{n^2}\|\j_0\|^2=r\left(1-\frac{1}{n}\right). $$ Since there is no path of length $\le k$ between any pair of vertices of $U$, $(Q_k(\A))_{u_iu_j}=0$ for any $i\neq j$. Thus, \begin{eqnarray*} 0 & = & \langle \B\f_U, \f_U\rangle = \left\langle \frac{(r-1)Q_k(\lambda_0)}{n}\j_0+\B\z_U, \frac{1}{n}\j_0+\z_U \right\rangle \\ & = & \frac{r(r-1)Q_k(\lambda_0)}{n} +\langle \B\z_U, \z_U\rangle \\ & \ge & \frac{r(r-1)Q_k(\lambda_0)}{n} - (r-1)\|\z_U\|^2 = \frac{r(r-1)}{n}(Q_k(\lambda_0) - n+1). \end{eqnarray*} Therefore, we get $$ Q_k(\lambda_0)=\frac{\alpha_k}{2}P_k(\lambda_0) +\frac{\alpha_k}{2}-1\le n-1 $$ and (\ref{k-indepen}) follows. From the above, notice that equality holds iff \begin{equation} \label{equality-0} \B\z_U=-(r-1)\z_U. \end{equation} By (\ref{spectral-decomp}), we infer that, if $\e_{u_i}=\frac{1}{n}\j+\z_i$, $\z_i\in \j^\bot$, represents the spectral decomposition of $\e_{u_i}$ in $\R^n\cong \bigoplus_{j=0}^d\Ker(\A-\lambda_j\I)$, $0\le i \le r-1$, then $\z_U=(\z_0^\top | \z_1^\top| \cdots |\z_{r-1}^\top)^\top$. Hence, (\ref{equality-0}) gives the $r$ vectorial equations: $$ \sum_{i=0, i\neq j}^{r-1} Q_k\z_i = -(r-1)\z_j\ \ \ (0\le j\le r-1) $$ which are equivalent to \begin{equation} \label{equality-1} Q_k\z_i= (r-2)\z_i-\sum_{j=0, j\neq i}^{r-1} \z_j\ \ \ (0\le i\le r-1). \end{equation} Let $H$ be the {\it Hoffman polynomial} defined by its values at $\ev\G$, namely $H(\lambda_0)=n$, $H(\lambda_i)=0$, $1\le i\le d$, and satisfying $H(\A)=\J$ (see Hoffman \cite{h63}.) Now we claim that the searched polynomial is $p=H-Q_k+(r-2)$, whose value at $\lambda_0$ is $p(\lambda_0)=n-(n-1)+(r-2)=r-1$. Indeed, using (\ref{equality-1}), we get \begin{eqnarray*} p\e_{u_i} & = & p\left(\frac{1}{n}\j+\z_i\right)=\frac{r-1}{n}\j-Q_k\z_i+(r-2)\z_i \\ & = &\frac{r-1}{n}\j +\sum_{j=0, j\neq i}^{r-1} \z_j = \sum_{j=0, j\neq i}^{r-1}\e_{u_j} =\e_{U\setminus\{u_i\}}\ \ \ (0\le i\le r-1), \end{eqnarray*} which concludes the proof of the theorem. \endproof For general $k$, the given bound (\ref{k-indepen}) is sharp. For instance, in \cite{fgy3} it was shown that the alternating polynomial $P$ ($k=d-1$) of an {\it $r$-antipodal distance-regular} graph on $n$ vertices satisfies $P(\lambda)=\frac{2}{r}n-1$, whence we get $\alpha_{d-1} \le r$. In the next section we prove again, for completeness, such a result on $P$ by using Theorem \ref{theo-k-indepen}, but first we will pay attention to some other straightforward consequences of the theorem. Using the language of Coding Theory, notice that (\ref{k-indepen}) yields a bound for the size of any code $C$ in $\G$ with minimum distance $\delta$ (that is the minimum distance between two distinct `code words' ---vertices of $\G$.) Namely, $$ |C|\le \frac{2n}{P_{\delta-1}(\lambda_0)+1}. $$ In the spirit of \cite{k}, where a spectral upper bound is given on the minimum distance between $t$ subsets of same size, we can consider the $t$-diameter $D_t$ defined by $$ D_t:= \max_{U\subset V, |U|=t} \{\min_{u,v\in U} \dist (u,v)\}, $$ as it was done in \cite{cds97,g97}. The standard diameter is then $D=D_2$. From our theorem we have the following result. \begin{coro} Let $\G$ be a regular graph on $n$ vertices, and with $t$-diameter $D_t$. Then, \begin{equation} \label{bound-Dt} P_k(\lambda_0)>\frac{2n}{t}-1\ \ \Rightarrow\ \ D_t\le k. \end{equation} \end{coro} \proof From the hypothesis and Theorem \ref{theo-k-indepen} we get $\alpha_k\frac{2\|\vecnu\|^2}{t}-1\ \ \Rightarrow\ \ D_t\le k. \end{equation} Spectral bounds on the $t$-diameter, in terms of the $i$-th largest eigenvalue (in absolute value) of the adjacency and Laplacian matrices can be found in Kahale \cite{k} and Chung, Delorme, and Sol\'e \cite{cds97}, respectively. \section{Antipodal Distance-Regular Graphs} In this section we study two spectral characterizations of antipodal distance-regular graphs. The fist one establishes that the distance-regular graphs which are antipodal are characterized by their eigenvalue multiplicities. The second characterization was already commented in the Introduction, and states that we can see from the spectrum of a regular graph, and the cardinalities of the ``extremal fibres" (the sets of antipodal vertices at extremal distance) whether the graph is an antipodal distance-regular graph. Let us begin by recalling some definitions and known results which are on the basis of our work. \subsection{Distance-regular graphs} A (connected) graph $\G$ with diameter $D$ is {\it distance-regular} if, for any two vertices $u$ and $v\in \G_k(u)$, $0\le k\le D$, the numbers $a_k(u)=|\G_k(u)\cap \G(v)|$, $b_k(u)=|\G_{k+1}(u)\cap \G(v)|$, and $c_k(u)=|\G_{k-1}(u)\cap \G(v)|$ do not depend on $u$ and $v$, but only on $k$. Some basic references dealing with this topic are Bannai and Ito \cite{bi93}, Biggs \cite{b93}, and Brouwer, Cohen and Neumaier \cite{bcn}. A well-known characterization of such graphs is the following: a graph $\G$, with adjacency matrix $\A$ and diameter $D$, is distance-regular if and only if, for any $0\le k\le D$, its distance-$k$ matrix $\A_k$ is a polynomial of degree $k$ in $\A$. Recently, Garriga, Yebra, and the author \cite{fgy3} showed that, if $\G$ is extremal and diametral, the condition on $\A_D$ suffices, as stated in the following theorem. \begin{theo} \label{charac-Ad} A graph $\G$ with adjacency matrix $\A$ and diameter $D$ is distance-regular if and only if $\G$ is extremal, diametral, and its distance-$D$ matrix $\A_D$ is a polynomial of degree $D$ in $\A$. \ \ \ $\Box$ \end{theo} From this result, and generalizing some results of Haemers and Van Dam \cite{ha96,vd96,vdh96} (the case $d=3$) , and Garriga, Yebra and the author \cite{fgy2} (the case $|\G_{d}(u)|=1$), the following spectral characterization was also obtained in \cite{fg2}: \begin{theo} \label{characterizationDRG} A regular graph $\G$ on $n$ vertices, with spectrum $\Spec \G =\{\lambda_0,\lambda_1^{m_1},\cdots,\lambda_d^{m_d}\}$, is distance-regular if and only if \begin{equation} \label{num-charac} |\G_{d}(u)|=\frac{n}{\pi_0^2\sum_{i=0}^{d}\frac{1}{m_i \pi_i^2}} \end{equation} for every vertex $u$ of $\G$. \ \ \ $\Box$ \end{theo} Notice that the cases $d=1,2$ are trivial, in the sense that every (connected) regular graph $\G$ with two or three different eigenvalues is distance-regular. More precisely, $\G=K_n$ if $d+1=2$, and $\G$ is strongly regular when $d+1=3$. See, for instance, Godsil \cite{g93}. \subsection{Antipodal graphs} Let us now turn our attention to the antipodal graphs. In this context, another consequence of Theorem \ref{theo-k-indepen} is the following result, already proved in \cite{fgy4} using a different approach (see also \cite{g97}.) \begin{propo} \label{prop-antipodals} Let $\G$ be an extremal $r$-antipodal regular graph, with $n$ vertices and diameter $D$, and let $\A_D$ be the adjacency matrix of $\G_D$. If $\A_D$ belongs to the algebra generated by $\A$, then $\A_D=\J - R(\A)$, where $R:=\frac{r}{2}P-\frac{r}{2}+1$ and $P$ is the alternating polynomial of $\Gamma$. \end{propo} \proof The first part of the proof goes as in \cite{fgy4}: We know that $\Spec\G_D=$ \linebreak $\{(r-1)^\sigma,-1^{n-\sigma}\}$, where $\sigma=n/r$ stands for the number of fibres. By the hypothesis, there exists a polynomial $p\in \R_d[x]$ such that $p(\A)=\A_D$, so that $p(\lambda_0)=r-1$ and $p(\lambda_i)\in\{r-1,-1\}$ for $1\le i\le d$. Since $\G$ is regular, the polynomial $R:=H-p\in \R_d[x]$ satisfies $R(\A)=\J-\A_D$ and hence $R(\lambda_0)=n-r+1$, $R(\lambda_i)\in \{1,1-r\}$ for $1\le i\le d$. Moreover, since each entry of $R(\A)$ corresponding to a diametral pair of vertices is zero, it must be $R\in \R_{d-1}[x]$. Let $P:=\frac{2}{r}R+1-\frac{2}{r}$. Then, $P(\lambda_0)=\frac{2n}{r}-1$, and $P(\lambda_i)=\pm 1$ for $i\neq 0$. The second part of the proof consists in proving that $P$ is indeed the alternating polynomial $P_{d-1}$ of $\G$. But, from the above, $r=\alpha_{d-1}=2n/(P(\lambda_0)+1)$, so that, using (\ref{k-indepen}) we get $P(\lambda_0)\ge P_{d-1}(\lambda_0)$ and hence $P= P_{d-1}$. \endproof An interesting example of graphs satisfying the above hypotheses are the $r$-antipodal distance-regular graphs. Indeed, they are extremal, $D=d$, and its `distance-$d$ polynomial' $p_d$ satisfies $\A_d=p_d(\A)$. Thus, from $p_d=H-\frac{r}{2}P+\frac{r}{2}-1$, we infer that their alternating polynomial satisfies $P(\lambda_0)=\frac{2n}{r}-1$ and hence \begin{equation} \label{value-of-r} r=\frac{2n}{P(\lambda_0)+1}=2n\left(\sum_{i=0}^d\frac{\pi_0}{\pi_i}\right)^{-1}, \end{equation} where we have used (\ref{P(lambda)}). As mentioned above, this property of antipodal distance-regular graphs was already proved in \cite{fgy4}. At the end of the section, we will see that this condition is also sufficient to assure that an $r$-antipodal (regular) graph is distance-regular. Next, we use the above results to give a characterization of those distance-regular graphs which are antipodal, in terms of their eigenvalue multiplicities. With this aim, note first that, from the above expression of $p_d$, we have $p_d(\lambda_i)=\frac{r}{2}((-1)^{i}+1)-1$ for $1\le i\le d$. \begin{theo} \label{coro-num-pseudo++} A distance-regular graph $\G$ on $n$ vertices, with spectrum $\Spec \G=$ \linebreak $\{\lambda_0,\lambda_1^{m_1},\ldots,\lambda_d^{m_d}\}$, is r-antipodal if and only if \begin{equation} \label{mult-r-antipod-graph} m_i=\frac{\pi_0}{\pi_i} \ \ \ ( i\ even); \ \ \ \ \ \ m_i=(r-1)\frac{\pi_0}{\pi_i} \ \ \ ( i\ odd). \end{equation} \end{theo} \proof It is well-known that the multiplicities of a distance-regular graph can be obtained from the distance-$d$ polynomial $p_d$ and the eigenvalues using the following formula: \begin{equation} \label{mult-disreg} m_i=\frac{\phi_0 p_d(\lambda_0)}{\phi_ip_d(\lambda_i)} \ \ \ (0\le i\le d) \end{equation} where $\phi_i:=\prod_{j=0, j\neq i}^d (\lambda_i-\lambda_j)=(-1)^{i}\pi_i$ (see, for instance, Bannai and Ito \cite{bi93}.) But, if $\G$ is $r$-antipodal we have already seen that $p_d(\lambda_i)=r-1$ when $i$ is even, and $p_d(\lambda_i)=-1$ when $i$ is odd, giving (\ref{mult-r-antipod-graph}). Conversely, from (\ref{mult-r-antipod-graph}) and (\ref{mult-disreg}) we get \begin{equation} \label{values-pd(Li)} p_d(\lambda_i)= p_d(\lambda_0)\ \ \ ( i\mbox{ even}); \ \ \ \ \ \ p_d(\lambda_i)=\frac{-p_d(\lambda_0)}{r-1} \ \ \ ( i\mbox{ odd}). \end{equation} To compute the value of $p_d(\lambda_0)$, we first notice that $$ 0= \tr \A_d=\tr (p_d(\A))=\sum_{i=0}^d m_i p_d(\lambda_i) = p_d(\lambda_0)\sum_{i=0}^d\frac{\phi_0}{\phi_i} $$ where we have used the value of $m_ip_d(\lambda_i)$, $0\le i\le d$, given by (\ref{mult-disreg}). Hence, $$ \sigma:= \sum_{i\mbox{ {\scriptsize even}}} \frac{\pi_0}{\pi_i} =\sum_{i\mbox{ {\scriptsize odd}}} \frac{\pi_0}{\pi_i} $$ and, as the multiplicities add up to $n$, $$ \sum_{i=0}^d m_i = \sigma + (r-1)\sigma = n $$ whence $\sigma=n/r$. Consequently, by substituting the multiplicities given by (\ref{mult-r-antipod-graph}) into (\ref{num-charac}), we get $$ p_d(\lambda_0)=|\G_d(u)|=n\left( \sum_{i\mbox{ {\scriptsize even}}} \frac{\pi_0}{\pi_i} + \frac{1}{r-1}\sum_{i\mbox{ {\scriptsize odd}}} \frac{\pi_0}{\pi_i}\right)^{-1} =\frac{n}{\sigma}\left(1+\frac{1}{r-1}\right)^{-1}= r-1. $$ Thus, by (\ref{values-pd(Li)}), the $(0,1)$-matrix $p_d(\A)$ has eigenvalues $r-1$ (with multiplicity $\sigma$) and $-1$ (with multiplicity $(r-1)\sigma$). Consequently, it must be the adjacency matrix of the graph constituted by several ($\sigma$) copies of $K_r$. In other words, $\G$ is $r$-antipodal, as claimed. \endproof The case $r=2$, which results in \begin{equation} \label{mult-2-antipodal} m_j=\frac{\pi_0}{\pi_j} \ \ \ (0\le j\le d), \end{equation} was studied in \cite{fgy2}. \begin{theo} Let $\G=(V,E)$ be a connected regular graph on $n$ vertices, with mesh of eigenvalues $\ev \G=\{\lambda_0,\lambda_1,\ldots,\lambda_d\}$. Then $\G$ is an $r$-antipodal distance-regular graph if and only if the distance-$d$ graph $\G_d$ is constituted by disjoint copies of the complete graph $K_r$ with $$ r=2n\left(\sum_{i=0}^d\frac{\pi_0}{\pi_i}\right)^{-1}. $$ \end{theo} \proof We have already proved necessity as a consequence of Proposition \ref{prop-antipodals}, from which we derived (\ref{value-of-r}). To prove sufficiency note that, by hypothesis, any vertex $u$ of $\G$ belongs to an $(d-1)$-independent set with $\alpha_{d-1}=r$ vertices. Thus, from Theorem \ref{theo-k-indepen}, there exists a polynomial $p$ of degree $d$ such that $p\e_u=\e_{\G_d (u)}$ for every $u\in V$. That is, $$ p(\A)=\A_d. $$ Consequently, since $\G$ is clearly both extremal and diametral, Theorem \ref{charac-Ad} applies, and $\G$ is an ($r$-antipodal) distance-regular graph. \endproof \noindent{\bf Acknowledgment.} Work supported in part by the Spanish Research Council (Comi\-si\'on Interministerial de Ciencia y Tecnolog\'\i a, CICYT) under projects TIC 92-1228-E and TIC 94-0592. I am indebted to the referee for helpful comments. \begin{thebibliography}{99} \bibitem{bi93} E. Bannai and T. Ito, {\it Algebraic Combinatorics I: Association Schemes.} Benjamin-Cummings Lecture Note Ser. {\bf 58}, London (1993). \bibitem{b93} N. Biggs, {\it Algebraic Graph Theory.} Cambridge University Press, Cambridge, UK, 1993. \bibitem{bcn} A. E. Brouwer, A. M. Cohen and A. Neumaier, {\it Distance-Regular Graphs.} Springer-Verlag, Berlin, 1989. \bibitem{cds97} F. R. K. Chung, C. Delorme, and P. Sol\'e, $k$-Diameter and spectral multiplicity, submitted. \bibitem{cds} D. M. Cvetkovi\'c, M. Doob and H. Sachs, {\it Spectra of Graphs---Theory and Applications.} Deutscher Verlag der Wissenschaften, Berlin, 1980; Academic Press, New York, 1980; second edition: 1982; Russian translation: Naukova Dumka, Kiev, 1984; third edition: Johann Ambrosius Barth, Heidelberg, 1995 \bibitem{vd96} E. R. van Dam, {\it Graphs with Few Eigenvalues.} Ph.D. Thesis, Tilburg University, 1996. \bibitem{vdh95} E. R. van Dam and W. H. Haemers, Eigenvalues and the diameter of graphs, {\it Linear and Multilinear Algebra} {\bf 39} (1995), 33--44. \bibitem{vdh96} E. R. van Dam and W. H. Haemers, A characterization of distance-regular graphs with diameter three, {\it J. Algebraic Combin.} {\bf 6} (1977), 299--303. \bibitem{f} M. A. Fiol, Eigenvalue interlacing and weight parameters of graphs, submitted. \bibitem{fg1} M. A. Fiol and E. Garriga, The alternating and adjacency polynomials, and their relation with the spectra and diameters of graphs, submitted. \bibitem{fg2} M. A. Fiol and E. Garriga, From local adjacency polynomials to locally pseudo-distance-regular graphs, {\it J. Combin. Theory Ser. B} {\bf 71} (1997), 162--183. \bibitem{fgy1} 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{fgy2} M. A. Fiol, E. Garriga and J. L. A. Yebra, From regular boundary graphs to antipodal distance-regular graphs, {\it J. Graph Theory}, to appear. \bibitem{fgy3} 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{fgy4} M. A. Fiol, E. Garriga and J. L. A. Yebra, Boundary graphs: The limit case of a spectral property (I), submitted. \bibitem{g97} E. Garriga, {\it Contribuci\'o a la Teoria Espectral de Grafs: Problemes M\`etrics i Distancia-Regularitat.} Ph.D. Thesis, Universitat Polit\`ecnica de Catalunya, 1997. \bibitem{g93} C. D. Godsil, {\it Algebraic Combinatorics.} Chapman and Hall, 1993. \bibitem{ha95} W. H. Haemers, Interlacing eigenvalues and graphs, {\it Linear Algebra Appl.} {\bf 226--228} (1995), 593--616. \bibitem{ha96} W. H. Haemers, Distance-regularity and the spectrum of graphs, {\it Linear Algebra Appl.} {\bf 236} (1996), 265--278. \bibitem{h63} A. J. Hoffman, On the polynomial of a graph, {\it Amer. Math. Monthly} {\bf 70} (1963) 30--36. \bibitem{k} N. Kahale, Isoperimetric inequalities and eigenvalues, {\it SIAM J. Discrete Math.} {\bf 10}, No. 1 (1997) 30--40. \end{thebibliography} \end{document}