%%%%%%%%%%%%%%% % A LaTeX file for a 29 page document%%%%%%%%%%%%%%%%%%%% % Upper-case A B C D E F G H I J K L M N O P Q R S T U V W X Y Z % Lower-case a b c d e f g h i j k l m n o p q r s t u v w x y z % Digits 0 1 2 3 4 5 6 7 8 9 % Exclamation ! Double quote " Hash (number) # % Dollar $ Percent % Ampersand & % Acute accent ' Left paren ( Right paren ) % Asterisk * Plus + Comma , % Minus - Point . Solidus / % Colon : Semicolon ; Less than < % Equals = Greater than > Question mark ? % At @ Left bracket [ Backslash \ % Right bracket ] Circumflex ^ Underscore _ % Grave accent ` Left brace { Vertical bar | % Right brace } Tilde ~ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \documentstyle[12pt]{article} %\oddsidemargin .5cm % EJC %\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{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 \bit{\begin{itemize}} \def \eit{\end{itemize}} \def \beq{\begin{equation}} \def \eeq{\end{equation}} \def\A{\mbox{\boldmath $A$}} \def\B{\mbox{\boldmath $B$}} \def\Bo{{\cal B}} \def\C{\mbox{\boldmath $C$}} \def\Cir{{\cal C}} \def\Co{\ns{C}} \def\D{\mbox{\boldmath $D$}} \def\E{\mbox{\boldmath $E$}} \def\Eb{{\cal E}} \def\Fb{{\sigma}} \def\Fbbar{\overline{\sigma}} \def\G{\Gamma} \def\H{\mbox{\boldmath $H$}} \def\I{\mbox{\boldmath $I$}} \def\J{\mbox{\boldmath $J$}} \def\K{\mbox{\boldmath $K$}} \def\M{{\cal M}} \def\Max{\mbox{\sc M}} \def\N{{\cal N}} \def\O{\mbox{\boldmath $O$}} \def\Path{{\cal P}} \def\P{{\mbox{\boldmath $P$}}} \def\U{\mbox{\boldmath $U$}} \def\V{\mbox{\boldmath $V$}} \def\R{\ns{R}} \def\Z{\ns{Z}} \def\d{\partial} \def\ds{\displaystyle} \def\dgr{{\rm dgr\,}} \def\ecc{\varepsilon} \def\exc{e} \def\e{\mbox{\boldmath $e$}} \def\f{\mbox{\boldmath $f$}} \def\eb{\mbox{\boldmath $\overline{e}$}} \def\alphabar{\overline{\alpha}} \def\ebar{\overline{e}} \def\gbar{\overline{g}} \def\ibar{\overline{i}} \def\pbar{\overline{p}} \def\qbar{\overline{q}} \def\mubar{\mu'} \def\vbar{\overline{v}} \def\Qbar{\overline{Q}} \def\wbar{\overline{w}} \def\ei{\mbox{\boldmath $e$}_i} \def\ej{\mbox{\boldmath $e$}_j} \def\eib{\overline{\mbox{\boldmath $e$}_i}} \def\j{\mbox{\boldmath $j$}} \def\jn{\frac{1}{n}\mbox{\boldmath $j$}} \def\u{{\mbox {\boldmath $u$}}} \def\v{{\mbox {\boldmath $v$}}} \def\w{{\mbox {\boldmath $w$}}} \def\wi{\mbox{\boldmath $w$}_i} \def\wj{\mbox{\boldmath $w$}_j} \def\x{\mbox{\boldmath $x$}} \def\z{\mbox{\boldmath $z$}} \def\zb{\mbox{\boldmath $\overline{z}$}} \def\zl{\mbox{\boldmath $z$}_l} \def\zi{\mbox{\boldmath $z$}_i} \def\zj{\mbox{\boldmath $z$}_j} \def\un{\frac{1}{\sqrt n}\mbox{\boldmath $u$}} \def\vecalpha{\mbox{\boldmath $\alpha$}} \def\vecalphai{\mbox{\boldmath $\alpha$}_i} \def\vecnu{\mbox{\boldmath $\nu$}} \def\vecrho{\mbox{\boldmath $\rho$}} \def\vec0{\mbox{\bf 0}} \def\Ker{\mathop{\rm Ker}\nolimits} \def\tr{\mathop{\rm tr}\nolimits} \def\S {\mathop{\rm S }\nolimits} \def\ds{\(\displaystyle} \def\matrixsigma{\mbox{\boldmath $\sigma$}} \pagestyle{myheadings} \markright{\sc the electronic journal of combinatorics 4 (1997), \#R21\hfill} %EJC \thispagestyle{empty} \begin{document} \title{ \vskip-.25cm %EJC Some Applications of the Proper and Adjacency Polynomials in the Theory of Graph Spectra \vskip-.25cm %EJC } \author{\baselineskip=5pt M.A. Fiol \\ {\small Departament de Matem\`atica Aplicada i Telem\`atica, Universitat Polit\`ecnica}\\ {\small de Catalunya,Jordi Girona, 1--3 , M\`odul C3, Campus Nord }\\ {\small 08034 Barcelona,Spain; email: {\tt fiol@mat.upc.es} } } \date{\small %EJC Submitted: February 22, 1997; Accepted: September 15, 1997. } \maketitle \begin{abstract} Given a vertex $u\in V$ of a graph $\G=(V,E)$, the (local) proper polynomials constitute a sequence of orthogonal polynomials, constructed from the so-called $u$-local spectrum of $\G$. These polynomials can be thought of as a generalization, for all graphs, of the distance polynomials for the distance-regular graphs. The (local) adjacency polynomials, which are basically sums of proper polynomials, were recently used to study a new concept of distance-regularity for non-regular graphs, and also to give bounds on some distance-related parameters such as the diameter. Here we develop the subject of these polynomials and gave a survey of some known results involving them. For instance, distance-regular graphs are characterized from its spectrum and the number of vertices at ``extremal distance" from each of their vertices. Afterwards, some new applications of both, the proper and adjacency polynomials, are derived, such as bounds for the radius of $\G$ and the weight $k$-excess of a vertex. Given the integers $k,\mu\ge 0$, let $\G_k^\mu(u)$ denote the set of vertices which are at distance at least $k$ from a vertex $u\in V$, and there exist exactly $\mu$ (shortest) $k$-paths from $u$ to each of such vertices. As a main result, an upper bound for the cardinality of $\G_k^\mu(u)$ is derived, showing that $|\G_k^\mu(u)|$ decreases at least as $O(\mu^{-2})$, and the cases in which the bound is attained are characterized. When these results are particularized to regular graphs with four distinct eigenvalues, we reobtain a result of Van Dam about 3-class association schemes, and prove some conjectures of Haemers and Van Dam, about the number of vertices at distance three from every vertex of a regular graph with four distinct eigenvalues ---setting $k=2$ and $\mu=0$--- and, more generally, the number of non-adjacent vertices to every vertex $u\in V$, which have $\mu$ common neighbours with it. \end{abstract} \begin{center}%EJC {\bf AMS subject classifications.} 05C50 {\small 05C38 05E30 05E35} \end{center} \section{Introduction} The interactions between algebra and combinatorics have proved to be a fruitful subject of study, as shown by the increasing amount of literature on the subject that has appeared in the last two decades. Some good references are the text of Bannai and Ito \cite{bi93}, Godsil's recent book \cite{g93}, and the very recent {\it Handbook of Combinatorics} \cite{ggl}. In particular, a considerable effort has been devoted to the use of algebraic techniques in the study of graphs as, for instance, the achievement of bounds for (some of) their parameters in terms of their (adjacency or Laplacian) spectra. Classic references dealing with this topic are the books of Biggs \cite{b93}, Cvetkovi\'c, Doob, and Sachs \cite{cds}, and the comprehensive text about distance-regular graphs of Brouwer, Cohen and Neumaier \cite{bcn}. (See also the surveys of Cvetkovi\'c and Doob \cite{cd} and Schwenk and Wilson \cite{sw}.) In this context, some of the recent work has been specially concerned with the study of metric parameters, such as the mean distance, diameter, radius, isoperimetric number, etc. See, for instance, the papers of Alon and Milman \cite{am85}, Biggs \cite{B80}, Chung et.al. \cite{c89,cfm94}, Van Dam and Haemers \cite{vdh95}, Delorme and Sol\'e \cite{ds91}, Kahale \cite{k97}, Mohar \cite{m91}, Quenell \cite{q94}, Sarnak \cite{s90}, and Garriga, Yebra, and the author \cite{fg1,fgy1,fgy5}. We must also mention here Haemers' thesis \cite{h80}, an account of which can be found in his recent paper \cite{ha95}. Somewhat surprisingly, in some of these works the study of the limit cases ---in which the derived bounds are attained--- has revealed the presence of high levels of structure in the considered graphs. See, for instance, the papers of Haemers and Van Dam, \cite{ha96,vdh96}, and Garriga, Yebra, and the author \cite{fg2,fg3,fgy2,fgy3}, and also the recent theses of Van Dam \cite{vd96}, Garriga \cite{g97} and Rodr\' \i guez \cite{r97}. In their study, Garriga and the author introduced two families of orthogonal polynomials of a discrete variable, constructed from the so-called local spectrum of the graph. The members of one of these families are called the ``proper polynomials," and can be seen as a generalization, for all graphs, of the distance polynomials for the distance-regular graphs. The other family, constituted by the ``adjacency polynomials," is closely related to the first one, since its members are basically sums of consecutive proper polynomials. Both families were mainly used to study a new concept of distance-regularity for non-regular graphs, and also to give bounds on some distance-related parameters such as the diameter and the radius \cite{fg1}. Here, after introducing these polynomials and recalling its main properties, we survey some of the main known results related to them. For example, a regular graph with $d+1$ different eigenvalues is distance-regular if, and only if, the number of vertices at distance $d$ from any given vertex is the value of a certain expression which only depends on the spectrum of the graph \cite{fg2}. Afterwards, we further investigate some new applications of these polynomials, deriving new bounds for the radius of a graph and the ``weight $k$-excess" of a vertex. Generalizing these results, and grouping ideas of Van Dam \cite{vd96}, and Garriga and the author \cite{fg2,fg3}, we also derive bounds for the cardinalities of some special vertex subsets, and study the limit cases in which such bounds are attained. The particularization of these results to the case of regular graphs with four distinct eigenvalues proves some conjectures of Haemers and Van Dam \cite{ha96,vdh96,vd96} In the rest of this introductory section we recall some basic concepts and results, and fix the terminology used throughout the paper. As usual, $\G =(V,E)$ denotes a (simple and finite) connected graph with {\it order} $n:=|V|$. For any vertex $u\in V$, $\G(u)$ denotes the set of vertices adjacent to $u$, and $\delta (u):=|\G(u)|$ stands for its {\it degree}. The {\it distance} between two vertices is represented by $\partial (u,v)$. The {\it eccentricity} of a vertex $u$ is $\ecc(u) :=\max_{v\in V}\partial(u,v)$, the {\it diameter} of $\G$ is $D(\G) :=\max_{u\in V}\ecc (u)$, and its {\it radius} is $r(\G) :=\min_{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_k$, $0\le k\le D$, is the graph on $V$ where two vertices are adjacent whenever they are at distance $k$ in $\G$. Thus, $\G_1(u)=\G(u)$ and $\G_1=\G$. The {\it $k$-neighbourhood} of $u$ is then defined as $N_k(u):=\bigcup_{l=0}^k \G_l (u)=\{v:\;\partial (u,v)\leq k\}$. A closely related parameter is the so-called {\it $k$-excess} of $u$, denoted by $\exc_k(u)$, which is the number of vertices which are at distance greater than $k$ from $u$, that is $e_k(u) :=|V\setminus N_k(u)|$. Then, trivially, $\exc_0(u)=n-1$ and $\exc_D(u)=\exc_{\ecc (u)}(u)=0$. Furthermore, note that $\exc_k(u)=0$ if and only if the eccentricity of $u$ satisfies $\ecc (u)\le k$. The name ``excess" is borrowed from Biggs \cite{B80}, where he gave a lower bound, in terms of the eigenvalues of $\G$, for the excess $\exc_r(u)$ of (any) vertex $u$ in a regular graph with girth $g=2r+1$ ($r$ is sometimes called the {\it injectivity radius} of $\G$, see \cite{q94}.) All the involved matrices and vectors are indexed by the vertices of $\G$. Moreover, for any vertex $u\in V$, $\e_u$ will denote the $u$-th unitary vector of the canonical base of $\R^n$. Besides, we consider $\A$, the adjacency matrix of $\G$, as an endomorphism of $\R^n$. A polynomial in the vector space of real polynomials with degree at most $k$, $p\in \R_k[x]$, will 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. The {\it adjacency} (or {\it Bose-Mesner}) {\it algebra} of $\A$, denoted by ${\cal A}(\A)$, is the algebra of all the matrices which are polynomials in $\A$. 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 $$ \S (\G) := \{\lambda_0,\lambda_1^{m_1},\ldots,\lambda_d^{m_d}\} $$ where the supraindexes denote multiplicities. Because of its special role, the largest (positive and with multiplicity one) eigenvalue $\lambda_0$ will be also denoted by $\lambda$. We will make ample use of the positive eigenvector associated to such an eigenvalue, which is denoted by $\vecnu=(\nu_1,\nu_2,\ldots,\nu_n)^\top$, and is normalized to have smallest entry 1. Thus, $\vecnu=\j$ when $\G$ is regular. We will denote by $\M$ the mesh constituted by all the distinct eigenvalues, that is $\M:=\{\lambda> \lambda_1>\cdots>\lambda_d \}$. It is well-known that the diameter of $\G$ satisfies $D \leq d=|\M|-1$ (see, for instance, Biggs \cite{b93}.) We consider the mapping $\vecrho: \Path (V) \rightarrow \R^n$ defined by $\vecrho U:=\sum_{u\in U} \nu_u \e_u$ for any vertex subset $U\neq \emptyset$, and $\vecrho \emptyset:={\bf 0}$. This corresponds to assigning some weights to the vertices of $\G$, in such a way that it becomes ``regularized" since the {\it weight degree} of each vertex $u$ turns out to be a constant: $$ \delta_{\rho}(u):= \frac{1}{\nu_u}\sum_{v\in \G(u)}\nu_v=\lambda. $$ This approach has already been used by Garriga, Yebra, and the author to derive bounds of some parameters of a graph from its spectrum ---such as the diameter \cite{fgy1,fgy5}, the $k$-excess \cite{fg2}, and the independence and chromatic numbers \cite{f96}--- and also to study a new distance-regularity concept for non-regular graphs \cite{fgy2,fg3}. In this context the author introduced in \cite{f96} the notion of ``weight parameter" of a graph, defined as follows. For each parameter of a graph $\Gamma$, say $\xi$, defined as the maximum [minimum] cardinality of a set $U\subset V$ satisfying a given property {\sf P}, we can define the corresponding {\it weight parameter}, denoted by $\xi^\star$, as the maximum [minimum] value of $\|\vecrho U\|^2$ of a vertex set $U$ satisfying {\sf P}. Note that, when the graph is regular, the parameters $\xi^\star$ and $\xi$ are the same. Otherwise, when we are dealing with non-regular graphs, the weight parameters are sometimes more convenient to work with, as it was shown in the above-mentioned papers. For instance, we will here consider the {\it weight $k$-excess} of a vertex $u$: $$ \exc_k^\star(u):=\|\vecrho (V\setminus N_k(u))\|^2=\|\vecnu\|^2-\|\vecrho N_k(u)\|^2, $$ and we also use the notion of pseudo-distance-regularity, which is defined as follows. Given a vertex $u\in V$ of a graph $\G$, with eccentricity $\ecc (u)=\ecc$, consider the partition $V=V_0\cup V_1\cup\cdots\cup V_{\ecc}$ where $V_k :=\G_k (u)$, $0\le k\le \ecc$. Then, we say that $\G$ is {\it pseudo-distance-regular} around vertex $u$ whenever the numbers $$ c_k(v):=\frac{1}{\nu_v}\sum_{w\in \G(v)\cap V_{k-1}} \nu_w, \hspace{.5cm} a_k(v):=\frac{1}{\nu_v}\sum_{w\in \G(v)\cap V_{k}} \nu_w, \hspace{.5cm} b_k(v):=\frac{1}{\nu_v}\sum_{w\in \G(v)\cap V_{k+1}} \nu_w, $$ defined for any $v\in V_k$ and $0\le k\le \ecc$ (where, by convention, $c_0(u)=0$ and $b_\ecc(v)=0$ for any $v\in V_\ecc$) do not depend on the considered vertex $v\in V_k$, but only on the value of $k$. In such a case, we denote them by $c_k$, $a_k$ and $b_k$ respectively. Then, the matrix $$ {\cal I}(u):=\left(\begin{array}{ccccc} 0 & c_1 & \cdots & c_{\varepsilon-1} & c_\varepsilon \\ a_0 & a_1 & \cdots & a_{\varepsilon-1} & a_\varepsilon \\ b_0 & b_1 & \cdots & b_{\varepsilon-1} & 0 \end{array}\right) $$ is called the {\it (pseudo-)intersection array} around vertex $u$ of $\G$. It is shown in \cite{fgy3} that this is a generalization of the concept of distance-regularity around a vertex (which in turn is a generalization of distance-regularity) that can be found, for instance, in \cite{bcn}. For example, the graph $\G=P_3\times P_3$, where $P_3$ denotes the path graph on three vertices $\{u_1,u_2,u_3\}$ and positive eigenvector $(\nu_{u_1},\nu_{u_2},\nu_{u_2})^\top=(1,\sqrt{2},1)^\top$, has positive eigenvector $\vecnu$ with entries $\nu_{(u_i,u_j)}=\nu_{u_i}\nu_{u_j}$, $i,j\in\{1,2,3\}$. Using this, it can be easily checked that $\G$ pseudo-distance-regular around the ``central" vertex $(u_2,u_2)$, and also around every ``corner" vertex $(u_i,u_j)$, $i,j\in\{1,3\}$, $i\neq j$ (the intersection arrays around a central vertex and a corner vertex being different.) For instance, the intersection array around $u=(u_2,u_2)$ is: $$ {\cal I}(u):=\left(\begin{array}{ccccc} 0 & \sqrt{2} & 2\sqrt{2} \\ 0 & 0 & 0 \\ 2\sqrt{2} & \sqrt{2} & 0 \end{array}\right). $$ Finally, recall that a (symmetric) {\it association scheme} with $d$ classes can be defined as a set of $d$ graphs $\G_i=(V, E_i)$, $1\le i\le d$, on the same vertex set $V$, with adjacency matrices $\A_i$ satisfying $\sum_{k=0}^d \A_k=\J$, with $\A_0 := \I$; and $\A_i\A_j=\sum_{k=0}^d p_{ij}^k \A_k$, for some integers $p_{ij}^k$, $0\le i,j,k\le d$. Then, following Godsil \cite{g93}, we say that the graph $\G_i$ is the $i$-th class of the scheme, and so we indistinctly use the words ``graph" or ``class" to mean the same thing. \section{The Proper and Adjacency Polynomials} In this section we introduce two orthogonal systems of polynomials and, after recalling their main properties, we study some of their (old and new) applications. These polynomials are constructed from a discrete scalar product whose points are eigenvalues of the graph and the corresponding weights a sort of (local) multiplicities which we introduce next. \subsection{The local spectrum} For each eigenvalue $\lambda_i$, $0\le i\le d$, let $\U_i$ be the matrix whose columns form an orthonormal basis for the eigenspace corresponding to $\lambda_i$, $\Ker(\A-\lambda_i\I)$. The {\it (principal) idempotents} of $\A$ are the matrices $\E_i:=\U_i\U_i^\top$ representing the orthogonal projections onto $\Ker(\A-\lambda_i\I)$. Thus, in particular, $\E_0=\frac{1}{\|\vecnu\|^2}\vecnu\vecnu^\top$. Therefore, such matrices satisfy the following properties (see Godsil \cite{g93}): \begin{itemize} \item[(a.1)] $\E_i\E_j=\left\{ \begin{array}{ll} \E_i & \mbox{ if } i=j \\ \vec0 & \mbox{ otherwise; } \end{array} \right.$ \item[(a.2)] $\A\E_i=\lambda_i\E_i$; \item[(a.3)] $p(\A)=\sum_{i=0}^d p(\lambda_i)\E_i$,\ \ $p\in \R[x]$. \end{itemize} Given a vertex $u\in V$ and an eigenvalue $\lambda_i$, Garriga, Yebra, and the author \cite{fgy3} defined the {\it ($u$-)local multiplicity} of $\lambda_i$ as $$ m_u(\lambda_i):=\|\E_i\e_u\|^2=(\E_i)_{uu} \ \ \ (0\le i\le d) $$ so that $m_u(\lambda_i)\ge 0$ and, in particular, $m_u(\lambda_0)=\frac{\nu_u^2}{\|\vecnu\|^2}$. Moreover, they showed that, when the graph is seen from a vertex, its local multiplicities play a similar role as the standard multiplicities. Thus, \begin{itemize} \item[(b.1)] \ds \sum_{i=0}^d m_u (\lambda_i) =\sum_{i=0}^d \|\E_i\e_u\|^2=\|\e_u\|^2=1$\ \ \ $(u\in V)$; \item[(b.2)] \ds \sum_{u\in V} m_u(\lambda_i)=\tr \E_i = m_i$\ \ \ $(0\le i \le d)$; \item[(b.3)] \ds \Cir_k (u) := (\A^k)_{uu}=\sum_{i=0}^d m_u(\lambda_i)\lambda_i^k$, \end{itemize} where $\Cir_k (u)$ is the number of closed $k$-walks going through vertex $u$. If $\mu_0(=\lambda)>\mu_1>\cdots>\mu_{d_u}$ represent the eigenvalues with non-null local multiplicities, we define the {\it ($u$-)local spectrum} as $$ \S_u(\G):= \{\lambda^{m_u(\lambda)},\mu_1^{m_u(\mu_1)},\ldots,\mu_{d_u}^{m_u(\mu_{d_u})}\}. $$ Moreover, we introduce the {\it (u-)local mesh} as the set $\M_u:=\{\lambda>\mu_1>\cdots>\mu_{d_u}\}$. Then it can be proved that the eccentricity of $u$ satisfies $\ecc (u) \leq d_u=|\M_u|-1$ (see \cite{fgy3}.) From the $u$-local spectrum we introduce in $\R_{d_u}[x]$ the {\it ($u$-)local scalar product} \begin{equation} \label{loc-escalar-prod} \langle f,g\rangle_u:=\sum_{i=0}^{d_u}m_u(\mu_i)f(\mu_i)g(\mu_i) \end{equation} whose relation with the (standard) Euclidean product $\langle \cdot\, ,\cdot \rangle$ is \begin{eqnarray*} \label{C-escalar} \langle f\e_u ,g\e_u \rangle = (f(\A)g(\A))_{uu} & = & \left(\sum_{i=0}^d f(\lambda_i)\E_i \sum_{j=0}^d g(\lambda_j)\E_j\right)_{uu} \\ \\ & = & \sum_{i=0}^{d} f(\lambda_i)g(\lambda_i) (\E_i)_{uu} = \langle f,g\rangle_u \end{eqnarray*} where we have used properties (a.3) and (a.1). In particular, the relation between the corresponding norms is $\|f\e_u\| = \|f\|_u$. Moreover, note that, according to property (b.1), the weight function $\rho_i:= m_u(\mu_i)$, $0\le i\le d$, of the scalar product (\ref{loc-escalar-prod}) is normalized in such a way that $\sum_{i=0}^d\rho_i=1$. \subsection{The proper polynomials} Let us consider an orthonormal system of polynomials $\{g_k:\dgr g_k=k, 0\le k\le d_u\}$ with respect to the above scalar product (\ref{loc-escalar-prod}). From these polynomials, and taking into account that $g_k(\lambda)\neq 0$ since the roots of $g_k$ are within the interval $(\mu_{d_u},\mu_0)$, we can define another orthogonal secuence by $p_k^u=g_k(\lambda) g_k$, $0\le k\le d_u$, which clearly satisfy the following orthogonal property \begin{equation} \label{ortoproperty} \langle p_k^u,p_l^u \rangle_u= \delta_{kl}p_k^u(\lambda)\ \ \ (0\le k,l\le d_u), \end{equation} so that $\|p_k^u\|_u^2=p_k^u(\lambda)$. Such a sequence, which uniqueness can be easily proved by using induction, will be called the {\it ($u$-)local proper orthogonal system}, and its members the {\it ($u$-)local proper polynomials}. As elements of an orthogonal system, such polynomials satisfy a three-term recurrence of the form \beq \label{recur1} xp_k^u=b_{k-1}p_{k-1}^u+a_kp_k^u+c_{k+1}p_{k+1}^u\ \ \ (0\le k\le d), \eeq where $a_k$, $b_k$ and $c_k$ are the corresponding Fourier coeficients of $xp_k^u$ in terms of $p_{k-1}^u$, $p_k^u$, and $p_{k+1}^u$ respectively ($b_{-1}=c_{d+1}=0$), initiated with $p_{-1}^u=0$ and $p_0^u=1$. (See, for instance, \cite{nsu91}.) Notice that the value of $p_0^u$ is a consequence of the fact that the weight function is normalized, since then $\|p_0^u\|^2=\sum_{i=0}^d\rho_i=1=p_0^u(\lambda)$. Using the above property of the weight function, Garriga and the author \cite{fg2,fg3,g97} proved the following result giving some alternative characterizations of these polynomials. \begin{lema} Given any vertex $u$ of a graph $\G$, there exists a unique orthogonal system $p_0^u(=1),p_1^u,\ldots, p_{d_u}^u$, characterized by any of the following conditions: \begin{itemize} \item[(a)] $\|p_k^u\|_u^2=p_k^u(\lambda)$; \item[(b)] $a_k+b_k+c_k=\lambda$ \ \ \ $(0\leq k\leq d_u)$; \item[(c)] $\sum_{k=0}^{d_u} p_k^u= \frac{\|\vecnu\|^2}{\nu_u^2\pi_0}\prod_{k=0}^{d_u}(x-\mu_k)$, \ where $\pi_0=\prod_{k=0}^{d_u}(\lambda-\mu_k)$. \ \ \ $\Box$ \end{itemize} \end{lema} In the same papers it was shown that the highest degree polynomial $p_{d_u}^u$ satisfies the following properties: \begin{itemize} \item[(c.1)] The $u$-local multiplicities of $\G$ are given by \begin{equation} \label{locmul} m_u(\mu_i)=\frac{\nu_u^2\phi_0 p_{d_u}^u (\lambda)}{\|\vecnu\|^2\phi_i p_{d_u}^u (\mu_i)} \ \ \ \ (0\le i\le d_u) \end{equation} where $\phi_i=\prod_{j=0(j\neq i)}^{d_u} (\mu_i-\mu_j)$; \item[(c.2)] The value at $\lambda$ of the highest degree polynomial is \begin{equation} \label{P_d(lambda)} p_{d_u}^u(\lambda)=\frac{\frac{1}{m_u^2(\lambda)\pi_0^2}} {\sum_{i=0}^{d_u}\frac{1}{m_u(\mu_i)\pi_i^2}} \end{equation} where $\pi_i=(-1)^i\phi_i=|\phi_i|$. \end{itemize} \begin{example} \label{P3xP3} Let $\G=P_3\times P_3$, the cartesian product of two 3-path graphs with vertex sets $\{u_1,u_2,u_3\}$, considered in the Introduction. Then the spectrum of $\G$ is $S(\G)=\{2\sqrt{2}^{1},\sqrt{2}^{2},0^3,-\sqrt{2}^{2},-2\sqrt{2}^{1}\}$, whereas the local spectrum of the central vertex $u=(u_2,u_2)$ is $S_u (\G)=\{2\sqrt{2}^{\frac{1}{4}},0^\frac{1}{2},-2\sqrt{2}^{\frac{1}{4}}\}$. From this, one can compute the $u$-local proper polynomials and their values at $\lambda=2\sqrt{2}$, giving: \begin{itemize} \item $p_0^u=1$, \ \ \ 1; \item $p_1^u=\frac{1}{\sqrt{2}}x$, \ \ \ 2; \item $p_2^u=\frac{1}{4}x^2-1$, \ \ \ 1; \end{itemize} \end{example} \begin{example} Let $\G=LP$, the line graph of the Petersen graph, with spectrum $S(\G)=\{4^1,2^5,-1^4,-2^5\}$. Then every vertex $u$ of $\G$ has local spectrum $S_u (\G)=\{4^{\frac{1}{15}}, 2^{\frac{1}{3}},-1^{\frac{4}{15}},-2^{\frac{1}{3}}\}$. Hence, the $u$-local proper polynomials and their values at $\lambda=4$ turn out to be: \begin{itemize} \item $p_0^u=1$, \ \ \ 1; \item $p_1^u=x$, \ \ \ 4; \item $p_2^u=x^2-x-4$, \ \ \ 8; \item $p_3^u=\frac{1}{4}(x^3-3x^2-4x+8)$, \ \ \ 2; \end{itemize} \end{example} The reader who is familiar with the theory of distance-regular graphs probably has already realized that the proper polynomials can be thought of as a generalization of the so-called ``distance polynomials." Thus, in the second example, the derived polynomials satisfy $$ p_k^u(\A)=\A_k\ \ \ (0\le k\le d_u) $$ where $\A_k$ stands for the adjacency matrix of $\G_k$, usually called the {\it $k$-th distance matrix of $\G$}. In other words, for each $k=0,1,\ldots, d_u$, the polynomial $p_k^u$ is the $k$-distance polynomial of $\G$ and, consequently, $\G$ is distance-regular (see, for instance, \cite{bcn}.) In fact, generalizing this result, Garriga, Yebra, and the author \cite{fgy3} showed that a graph $\G$ is pseudo-distance-regular around a vertex $u$, with eccentricity $\ecc (u)=\ecc$, if and only if there exist the {\it ($u$-)local distance polynomials} $p _k^u$, $\dgr p_k^u=k$, satisfying \begin{equation} \label{loc-dist-pol} p_k^u\e_u=\frac{1}{\nu_u}\vecrho V_k\, , \ \ \ p_k^u (\lambda)=\frac{1}{\nu_u^2}\|\vecrho V_k\|^2 \ \ \ (0\le k\le \ecc) \end{equation} (the latter equality being a consequence of the former) where $V_k=\G_k(u)$; and that, as suggested by the notation, such polynomials coincide, in fact, with the proper polynomials. In addition, using property (c.2) and the adjacency polynomials defined bellow, Garriga and the author \cite{fg2} gave the following numeric characterization of pseudo-distance-regularity. (A similar characterization for ``completely regular" codes \cite{n92} can be found in \cite{fg3}.) \begin{theo} \cite{fg2} \label{num-charac-pdr} A graph $\G$ is pseudo-distance-regular around a vertex $u$, with local spectrum $\S_u(\G)$ as above, if and only if \begin{equation} \label{charac-2bis} \frac{1}{\nu_u^2}\|\vecrho V_{d_u}\|^2=p_{d_u}^u(\lambda)=\frac{\frac{1}{m_u^2(\lambda)\pi_0^2}} {\sum_{i=0}^{d_u}\frac{1}{m_u(\mu_i)\pi_i^2}} \end{equation} where $\pi_i=\prod_{j=0(j\neq i)}^{d_u}|\mu_i-\mu_j|$, $0\le i\le d_u$. \ \ \ $\Box$ \end{theo} As an example of application of the above result, let us consider again the graph $\G=P_3\times P_3$ ``seen" from the vertex $u=(u_2,u_2)$ with $\nu_u=2$ (Example \ref{P3xP3}.) Then, $V_{d_u}=V_2$ consists of the four corner vertices $(u_i,u_j)$, $i,j\in\{1,3\}$, $i\neq j$, with $\nu_{(u_i,u_j)}=1$, giving $\frac{1}{\nu_u^2}\|\vecrho V_{2}\|^2=1=p_{2}^u(\lambda)$. Consequently, $\G$ is pseudo-distance regular around $u$, as claimed in the Introduction. \subsection{The adjacency polynomials} The consideration of the adjacency polynomials can be motivated with the following result given in the aforementioned paper. \begin{theo} \cite{fg2} \label{basic-result} Let $u$ be a vertex of a graph $\G$, with local mesh of eigenvalues $\M_u=\{\lambda >\mu_1>\cdots>\mu_{d_u}\}$. Let $P$ be a polynomial of degree $k$, $0\le k\le d_u$, such that $\|P\|_u \le 1$. Then \begin{equation} \label{basic-inequal} P (\lambda)\le \frac{1}{\nu_u}\|\vecrho N_k(u)\| , \end{equation} and equality is attained if and only if \begin{equation} \label{tight} P\e_u=\frac{1}{\|\vecrho N_k(u)\|}\vecrho N_k(u), \end{equation} in which case $\|P\|_u=1$. Moreover, if this is the case and $k=d_u-1$, $\ecc (u)=d_u$, then $\G$ is pseudo-distance-regular around vertex $u$.\ \ \ $\Box$ \end{theo} This result leads, in a natural way, to the study of the polynomials which optimize the result in (\ref{basic-inequal}), so that they are the only possible candidates to satisfy (\ref{tight}). In other words, we are interested in finding the polynomial(s) $P$ of degree $\le k$ such that $\|P\|_u\le1$ and $P (\lambda)$ is maximum. The study of these polynomials, called the {\it ($u$-)local adjacency polynomials} and denoted by $Q_k^u$, $0\le k\le d_u$, was done in \cite{fg2}, and their basic properties are the following: \begin{itemize} \item[(d.1)] There exists a unique local adjacency polynomial $Q_k^u$, with $\dgr Q_k^u=k$, for any $k=0,1,\ldots,d_u$, and $\|Q_k^u\|_u=1$; \item[(d.2)] The local adjacency polynomials of degrees $0$, $1$, and $d_u$, and their values at $\lambda$, are the following: \begin{itemize} \item[$\bullet$] $Q_0^u=1$;\ \ \ $Q_0^u(\lambda)=\|\e_u\|=1$; \item[$\bullet$] $Q_1^u=\frac{1}{\sqrt{\frac{\lambda^2}{\delta(u)}+1}} \left(\sqrt{\frac{\lambda}{\delta(u)}x+1}\right)$;\ \ \ $Q_1^u (\lambda)=\sqrt{\frac{\lambda^2}{\delta(u)}+1}$ \item[$\bullet$] $Q_{d_u}^u=\frac{\|\vecnu\|}{\nu_u\pi_0}\prod_{i=1}^{d_u} (x-\mu_i)$, \ where $\pi_0=\prod_{i=1}^{d_u} (\lambda-\mu_i)$; \ \ \ $Q_{d_u}^u(\lambda)=\frac{1}{\nu_u}\|\vecnu\|$; \end{itemize} \item[(d.3)] In general, the local adjacency polynomials can be computed from the local proper orthogonal system $\{p_k^u\}$ in the following way: \begin{itemize} \item[$\bullet$] $Q_k^u=\frac 1{\sqrt{q_k^u(\lambda)}}q_k^u$ \ \ \ $(0\le k\le d_u)$, \ where $q_k^u:=\sum_{l=0}^k p_l^u$; \end{itemize} \item[(d.4)] $1=Q_0^u (\lambda)\frac{1}{\nu_u}\sqrt{\|\vecnu\|^2-1}\ \Rightarrow \ \ecc(u)\le k. $$ \end{coro} The following simple example is also drawn from \cite{fg1}: \begin{example} Let $\G$ be the graph obtained from $K_4$ by deleting an edge. Then $\G$ has spectrum and positive eigenvector $$ \textstyle {\rm S}(\G)=\{\frac{1}{2}(1+\sqrt{17}),0,-1,\frac{1}{2}(1-\sqrt{17})\}, \ \ \ \vecnu=(1,\frac{1}{2}(1+\sqrt{17}),1,\frac{1}{2}(1+\sqrt{17}))^\top, $$ respectively (the 1 entries of $\vecnu$ correspond to the vertices of degree 2). Then, $\|\vecnu\|^2=\frac{17+\sqrt{17}}{4}$ and, if $u$ is a vertex of degree 3 we get, from (b.2), $$ Q_1^u=\frac{(\sqrt{17}+1)x+12}{\sqrt{198+6\sqrt{17}}} $$ giving $Q_1^u(\lambda) = 1.6833\ldots$ Therefore, since $\frac{1}{\nu_u}\sqrt{\|\vecnu\|^2-1} = 1.6154\ldots$, Corollary \ref{ecc(u)} gives $e(u)=1$. \end{example} \subsection{The regular case} Let $\G=(V,E)$ be a graph with $n$ vertices and $m$ edges. Then we say that $\G$ is \linebreak {\it ($u$-)locally regular} if vertex $u$ has degree $\delta(u)=\frac{2m}{n}$. Thus, $\G$ is regular iff it is $u$-locally regular for every $u\in V$. Similarly, we say that a graph $\G$ with spectrum $\S (\G) = \{\lambda_0,\lambda_1^{m_1},\ldots,\lambda_d^{m_d}\}$ is {\it ($u$-)locally spectrum-regular} when the $u$-local multiplicities of each eigenvalue satisfy \begin{equation} \label{mult-loc-spec-reg} m_u(\lambda_i)=\frac{m_i}{n}\qquad (0\le i\le d). \end{equation} (Thus, $d_u=d$.) Note that, from property (b.3) with $k=2$, if $\G$ is $u$-locally spectrum-regular then $\G$ is also $u$-locally regular. Associated to the values in (\ref{mult-loc-spec-reg}) we can now consider what we call the {\it average scalar product:} \begin{equation} \label{ave-escalar-prod} \langle f,g\rangle_\G:=\sum_{i=0}^{d}\frac{m_i}{n}f(\lambda_i)g(\lambda_i), \end{equation} since it is the average over $V$ of the local scalar products $\langle f,g\rangle_u$: \begin{eqnarray} \label{aver=aver-esc-prod} \nonumber \frac{1}{n} \sum_{u\in V}\langle f,g\rangle_u & = &\frac{1}{n}\sum_{u\in V}\sum_{i=0}^{d}m_u(\lambda_i)f(\mu_i)g(\mu_i) \\ & = & \sum_{i=0}^{d}f(\mu_i)g(\mu_i)\frac{1}{n}\sum_{u\in V}m_u(\lambda_i) = \langle f,g\rangle_\G \end{eqnarray} where we have used property (b.2). Therefore, since $\langle f,g\rangle_u=(f(\A)g(\A))_{uu}$, an alternative definition of this scalar product would be $\langle f,g\rangle_\G =\frac{1}{n} \tr (f(\A)g(\A))$. Since the weight function of such a scalar product is also normalized, $\sum_{i=0}^d\frac{m_i}{n}=1$, we can also consider its corresponding proper and adjacency polynomials, denoted by $p_k$ and $Q_k$, $0\le k\le d$, respectively, which will be called the {\it average (proper} and {\it adjacency) polynomials.} Using them we can now give the following new result. \begin{theo} \label{basic-result-ave} Let $\G=(V,E)$ be a graph on $n$ vertices, with spectrum $\S(\G)=$ \linebreak $\{\lambda,\lambda_1^{m_1},\ldots,\lambda_d^{m_d}\}$. Then, for each given $k$, $0\le k\le d$, there exists a vertex $u\in V$ such that the average adjacency polynomial of $\G$ satisfies $\|Q_k\|_u\le 1$ and \begin{equation} \label{basic-inequal-ave} \|\vecrho N_k(u)\|\ge \nu_u Q_k(\lambda). \end{equation} If equality is attained, then $Q_k=Q_k^u$ and \begin{equation} \label{tight-ave} \vecrho N_k(u) = \|\vecrho N_k(u)\| Q_k\e_u. \end{equation} Moreover, if $k=d-1$ and $\ecc (u)=d$, then $\G$ is $u$-locally spectrum-regular and pseudo-distance-regular around $u$. \end{theo} \proof We know that the average adjacency polynomial satisfies $\|Q_k\|_\G=1$. Then, from (\ref{aver=aver-esc-prod}) with $f=g=Q_k$, $$ \sum_{u\in V} \|Q_k\|_u^2 = n\|Q_k\|_\G^2 = n. $$ Hence, there must be some vertex, say $u$, for which $\|Q_k\|_u\le 1$, and Theorem \ref{basic-result} gives the lower bound (\ref{basic-inequal-ave}) for $\|\vecrho N_k(u)\|$. If such a bound is attained, then, by the same theorem and property (d.1), the polynomial $Q_k$ must coincide with the $u$-local adjacency polynomial $Q_k=Q_k^u$, $\|Q_k\|_u=1$, and (\ref{tight-ave}) holds. Furthermore, if $k=d-1=\ecc(u)-1$, we must have $d_u=d$, since $d=\ecc(u) \le d_u \le d$, and hence property (d.3) gives $Q_{d}^u=\frac{\|\vecnu\|}{\nu_u\pi_0}\prod_{i=1}^{d} (x-\lambda_i)= Q_d$. Thus, applying property (d.2) we have, for $k=d-1,d$, $$ q_k^u=\sqrt{Q_k^u(\lambda)}Q_k^u=\sqrt{Q_k(\lambda)}Q_k= q_k, $$ and hence $p_{d}^u=q_d^u-q_{d-1}^u=q_d-q_{d-1}=p_d$. Consequently, we infer from (\ref{locmul}) that the ``weight functions'' of both the local and average scalar products must coincide, $m_u(\lambda_i)=\frac{m_i}{n}$, $0\le i\le d$, and $\G$ is $u$-locally spectrum-regular. Finally, Theorem \ref{basic-result} assures that $\G$ is also pseudo-distance-regular around vertex $u$. \endproof Note that, in general, the vertex $u$ depends on the value of $k$. Two straightforward consequences of the above theorem are the following. \begin{coro} \label{coro-exc} Let $\G$ be a graph as above. Then, for each given $0\le k\le d$, there exists a vertex $u\in V$ with weight $k$-excess $$ \exc_k^\star(u)\le \|\vecnu\|^2-\nu_u^2 Q_k^2(\lambda) $$ where $Q_k$ is the average adjacency polynomial. \end{coro} \proof Use the definition of $\exc_k^\star(u)$ and (\ref{basic-inequal-ave}). \endproof \begin{coro} Let $\G$ be a graph as above, with radius $r(\G)$ and average adjacency polynomial $Q_k$. Then, $$ Q_k^2(\lambda) > \|\vecnu\|^2-1\ \Rightarrow \ r(\G) \le k. $$ \end{coro} \proof Using the hypothesis and Corollary \ref{coro-exc}, we infer that there exist a vertex $u$ such that such that $\exc_k^\star(u)\le \|\vecnu\|^2-\nu_u^2Q_k^2(\lambda)\le \|\vecnu\|^2-Q_k^2(\lambda)<1$. Therefore, since $e_k(u)\le e_k^\star (u)$, we must have $e_k(u)=0$ and hence $r(\G)\le \ecc(u)\le k$. \endproof Note the similarity between the above result and Corollary \ref{ecc(u)}. \section{Partially walk-regular graphs} Given an integer $\tau> 0$, a graph $\G$ is said to be {\it $\tau$-partially walk-regular} if the number $\Cir_k (u)=(\A^k)_{uu}$ of closed walks of length $k$, $0\le k\le \tau$, through a vertex $u\in V$ does not depend on $u$. For instance, every $\delta$-regular graph with girth $g$ is $(g-1)$-partially walk-regular, since in this case, for any $u\in V$ and $0\le k\le g-1$, we have $\Cir_k(u)=\Psi (k)$, where $\Psi (k)$ denote the number of closed walks of legth $k$ which go through the root of a (internally) $\delta$-regular tree of depth $\ge k/2$ (hence, $\Psi (k)=0$ if $k$ is odd.) Notice that, since $\I,\A,\ldots, \A^d$ is a basis for ${\cal A}(\A)$, if $\G$ is $\tau$-partially walk-regular with $\tau\ge d$, then all the matrices in such a basis have constant diagonal, and hence $\G$ is $\tau$-partially walk-regular for any integer $\tau$. In this case $\G$ is simply called {\it walk-regular}, a concept introduced by Godsil and McKay \cite{gMc}. These authors proved that walk-regular graphs are also characterized by the fact that all the subgraphs obtained by removing a vertex from $\G$ are cospectral, see also Godsil \cite{g93}. As it is easy to show, examples of walk-regular graphs are the vertex-transitive and/or distance-regular graphs. Let $\G$ be a $\tau$-partially walk-regular graph with $\tau n-1\ \Rightarrow \ D(\G) \le k$. \ \ \ $\Box$ \end{theo} When $\G$ is spectrum-regular, the above statements were already given in \cite{fg1,fg2}. Moreover, when $d=3$ Theorem \ref{bounds-spec-reg}(b) proves a conjecture of Haemers \cite{ha96} (see also \cite{vdh96}) about the number of vertices at distance two from every vertex of a regular graph with four distinct eigenvalues. \begin{coro} Let $\G=(V,E)$ be a $\delta$-regular graph with four distinct eigenvalues, $\S(\G)= $ \linebreak $\{\lambda,\lambda_1^{m_1},\lambda_2^{m_2},\lambda_3^{m_3}\}$. Then, the number of vertices at distance two from every vertex $u\in V$ is lower-bounded by $$ |\G_2(u)| \ge n-1-\delta-\frac{n}{\pi_0^2\sum_{i=0}^3\frac{1}{m_i\pi_i^2}} $$ where $\pi_i=\prod_{j=0(j\neq i)}^3 |\lambda_i-\lambda_j|$. \end{coro} \proof For every vertex $u\in V$ we have $|\G_2(u)|=n-1-\delta-|\G_3(u)|$. Hence, since $\G$ is spectrum-regular by Lemma \ref{lema-spec-reg}, the result follows from Theorem \ref{bounds-spec-reg}(b). \subsection{Partially distance-regular graphs} An example of partially walk-regular graphs are those graphs bearing a `partial distance-regularity' around every one of their vertices, studied in \cite{p91}. More precisely, a graph $\G$, with adjacency matrix $\A$ and $d+1$ distinct eigenvalues, is said to be {\it ($d'$-)partially distance-regular} if, for any $0\le k\le d'$, there exist a polynomial $p_k$ of degree $k$ such that $p_k(\A)=\A_k$, the $k$-th distance matrix of $\G$. In fact, any $d'$-partially distance-regular graph is also $(2d')$-partially walk-regular and, as expected, the above polynomials $p_k$ are again the proper polynomials, see \cite{fg1}. By way of example, note that a graph is $1$-partially distance-regular iff it is regular. At the other extreme, a $(d-1)$-partially distance-regular graph is also $d$-partially distance-regular (since $\A_d=\J-\sum_{k=0}^{d-1}\A_k=(H-q_{d-1})(\A)$,) which is the same as distance-regular. When $\G$ is a regular graph with girth $g$, simple reasoning shows that it is $d'$-partially distance-regular graph with $d'\ge \lfloor\frac{g-1}{2} \rfloor$, see Biggs \cite{B80,b93}. In the case of odd $g$, say $g=2r+1$, Biggs \cite{B80} proved that the $r$-excess of any vertex $u$ satisfies \begin{equation} \label{biggs-excess} \exc_r(u)\ge \|q_r\|_\infty \end{equation} where $q_r=\sum_{k=0}^r p_k$ and $\|q_r\|_\infty:= \max_{1\le i\le d}\{|q_r(\lambda_i)|\}$. In fact, the same reasoning used in that paper proves that (\ref{biggs-excess}) also applies for an $r$-partially distance-regular graph. As a conclusion note that, from Theorem \ref{bounds-spec-reg}(a) and the above comments, the $k$-excess of any vertex of a $k$-partially distance-regular graph satisfies $$ \|q_k\|_\infty \le \exc_k(u) \le n- q_k(\lambda). $$ As another consequence of Theorem \ref{basic-result}, we can give the following characterization of $d'$-partially distance-regular graphs. \begin{theo} \label{num-charac-tau-dr} Let $\G$ be a regular graph, with spectrum $\S(\G)=\{\lambda,\lambda_1^{m_1},\ldots,\lambda_d^{m_d}\}$, and average proper polynomials $p_k$, $0\le k\le d$, with leading coefficients $a_k$. Then $\G$ is $d'$-partially distance-regular if and only if, for any $2\le k\le d'$, the number of vertices at distance $k$ from every vertex is $n_k=p_k(\lambda)$. \end{theo} \proof We only prove sufficiency. From the hypothesis, the average adjacency polynomials $Q_k=\frac{1}{\sqrt{q_k(\lambda)}}q_k$ (see property (d.2)) satisfy $$ Q_k(\lambda)= \sqrt{q_k(\lambda)}= \sqrt{|N_k(u)|}=\|\vecrho N_k(u)\| $$ for every $u\in V$ and $0\le k\le d'$ (the cases $k=0,1$ are trivial.) Then, by the converse of Theorem \ref{basic-result}, it must be $\|Q_k\|_u\ge 1$. On the other hand, in the proof of Theorem \ref{basic-result-ave} we have seen that $\sum_{u\in V} \|Q_k\|_u^2=n$. Consequently, we must have $\|Q_k\|_u=1$ and, using again Theorem \ref{basic-result}, we infer that $$ Q_k\e_u=\frac{1}{\|\vecrho N_k(u)\|}\vecrho N_k(u)=\frac{1}{\sqrt{|N_k(u)|}}\vecrho N_k(u), $$ or $p_k\e_u=\vecrho \G_k(u)$ for every $u\in V$ and $0\le k\le d'$. But this is equivalent to $p_k(\A)=\A_k$, for any $0\le k\le d'$, and $\G$ is $d'$-partially distance-regular. \endproof \section{Bounding Special Vertex Sets} Let $\G=(V,E)$ be a regular graph with four distinct eigenvalues, so that $\G$ is spectrum-regular and $D(\G)\le 3$. Generalizing the work of Haemers and Van Dam \cite{vdh96} about distance-regular graphs with diameter three to 3-class association schemes, the latter author \cite{vd96} studied some bounds for the number of non-adjacent vertices to a (generic) vertex $u\in V$, that have a fixed number $\mu$ of common neighbours with $u$. The best bound he gave generalized that conjectured by Haemers in \cite{ha96} ---since for $\mu=0$ such a number clearly is $|\G_3(u)|$. Van Dam showed that such a bound applied when $\G$ satisfied some additional conditions, and conjectured that this was always the case. Moreover he showed that the bound was attained for every vertex if and only if $\G$ is the (connected) graph of a 3-class association scheme. Following these work, and using again the proper and adjacency polynomials, in this section we study bounds for the more general vertex subsets $\G_k^\mu(u)$, defined below. Also, the ``extremal cases" are characterized. When the results are particularized to spectrum-regular graphs, a proof of Van Dam's conjecture is obtained. Let $u\in V$ be a vertex with eccentricity $\ecc(u)=\ecc$. Given the integers $k,\mu$ such that $0\le k\le \ecc$ and $\mu\ge 0$, let $\G_k^\mu(u)$ denote the set of vertices which are at distance at least $k$ from $u\in V$ and there exist exactly $\mu$ (shortest) $k$-paths from $u$ to each of such vertices. Note that $\G_k^0(u)=V\setminus N_k(u)$, and if $\mu \neq 0$, then $\G_k^\mu(u)$ contains only vertices at distance $k$ from $u$, so that we get the partition $\G_k(u)=\cup_{\mu\ge 1} \G_k^\mu(u)$. The next theorem gives an upper bound for $\|\vecrho \G_k^\mu(u)\|^2$, and hence also for the cardinality of $\G_k^\mu(u)$. \begin{theo} \label{main-theo} Let $u$ be a vertex of a graph $\G$, with eccentricity $\ecc (u)= \ecc$, and local mesh of eigenvalues $\M_u=\{\lambda >\mu_1>\cdots>\mu_{d_u}\}$. Let $P$ be a polynomial of degree $k< d_u$ with leading coefficient $c_k$ such that $\nu_uP(\lambda)=1+\|\vecnu\|^2c_k\mu$. Then, for any given integer $\mu > 0$, \begin{equation} \label{gen-bound-2} \|\vecrho \G_k^\mu(u)\|^2\le \frac{\|\vecnu\|^2\left(\|\vecnu\|^2\|P\|_u^2-\nu_u^2P^2(\lambda) \right)} {1+ \|\vecnu\|^2\|P\|_u^2-\nu_u^2P^2(\lambda) }\, , \end{equation} where the equality is attained if and only if $n_k^\mu:=|\G_k^\mu(u)|=\|\vecrho \G_k^\mu(u)\|^2$ and either \begin{itemize} \item[(a)] when $k= \ecc$: \begin{equation} \label{gen-tight} P\e_u = \frac{\nu_u P(\lambda)(\|\vecnu\|^2-n_{ \ecc}^\mu)+n_{ \ecc}^\mu }{\|\vecnu\|^2(\|\vecnu\|^2-n_{ \ecc}^\mu)}\vecnu - \frac{1}{\|\vecnu\|^2-n_{ \ecc}^\mu}\vecrho\G_{\ecc}^\mu(u)\, ; \end{equation} \item[(b)] when $k<\ecc$: \begin{equation} \label{restric-tight} P\e_u = - \frac{1}{\|\vecnu\|^2-n_k}\vecrho V_k\, , \end{equation} where $V_k=\G_k(u)=\G_k^\mu (u)$ and \begin{equation} \label{restric-equality} n_k: = |V_k| = \frac{\|\vecnu\|^2\nu_uP(\lambda)}{\nu_uP(\lambda)-1 }\, , \end{equation} in which case \begin{equation} \label{nu-ck-mu} \frac{\|P\|_u^2}{P(\lambda)}=\nu_u c_k \mu. \end{equation} \end{itemize} \end{theo} \proof First, let $P$ be any polynomial with degree $k< d_u$ and assume $\mu\ge 0$ ($\mu >0$ if $k= \ecc$.) Let $U:=\G_k^\mu(u)$. From the following spectral decompositions of $\vecrho u=\nu_u\e_u$ and $\vecrho U=\sum_{v\in U}\nu_v\e_v$: $$ \vecrho u=\frac{\nu_u^2}{\|\vecnu\|^2}\vecnu +\z, \ \ \ \vecrho U=\frac{\|\vecrho U\|^2}{\|\vecnu\|^2}\vecnu +\z' $$ where $\z,\z' \in \vecnu^\bot$, we obtain $P\vecrho u=\frac{\nu_u^2 P(\lambda)}{\|\vecnu\|^2}\vecnu +P\z$ and so \begin{eqnarray} \label{normPz} \|P\z\|^2 & = & \|P\vecrho u\|^2-\frac{\nu_u^4 P^2(\lambda)}{\|\vecnu\|^2} =\nu_u^2\left( \|P\|_u^2-\frac{\nu_u^2 P^2(\lambda)}{\|\vecnu\|^2}\right ); \\ \label{normz'} \|\z'\|^2 & = & \|\vecrho U\|^2\left(1- \frac{\|\vecrho U\|^2}{\|\vecnu\|^2}\right). \end{eqnarray} Hence, \begin{eqnarray*} c_k\mu\nu_u\|\vecrho U\|^2 & \ge & c_k\mu\nu_u\sum_{v\in U} \nu_v = \langle P\vecrho u, \vecrho U\rangle = \left\langle \frac{\nu_u^2P(\lambda)}{\|\vecnu\|^2}\vecnu +P\z,\, \frac{\|\vecrho U\|^2}{\|\vecnu\|^2}\vecnu +\z' \right\rangle \\ & = & \frac{\nu_u^2\|\vecrho U\|^2}{\|\vecnu\|^2}P(\lambda) +\langle P\z, \z' \rangle \ge \frac{\nu_u^2\|\vecrho U\|^2}{\|\vecnu\|^2}P(\lambda) - \|P\z\|\|\z'\| \\ & = & \frac{\nu_u^2\|\vecrho U\|^2}{\|\vecnu\|^2}P(\lambda) - \nu_u\|\vecrho U\|^2 \sqrt{\left( \|P\|_u^2-\frac{\nu_u^2 P^2(\lambda)}{\|\vecnu\|^2}\right) \left(\frac{1}{\|\vecrho U\|^2}- \frac{1}{\|\vecnu\|^2}\right)} \end{eqnarray*} Simplifying and rearranging the terms, we get \begin{equation} \label{inter-inequal} \frac{\|\vecnu\|^2}{\|\vecrho U\|^2}\ge \frac{\left( \nu_u P(\lambda)-\|\vecnu\|^2c_k\mu\right)^2} {\|\vecnu\|^2\|P\|_u^2-\nu_u^2P^2(\lambda)} + 1, \end{equation} where $$ \Phi:= \|\vecnu\|^2\|P\|_u^2-\nu_u^2P^2(\lambda) = \sum_{i=1}^{d_u}m_u(\mu_i) P^2(\mu_i) >0 $$ since $m_u(\lambda)=\frac{\nu_u^2}{\|\vecnu \|^2}$ and $\dgr P\cdots>\mu_{d_u}\}$.) Then, solving for $\|\vecrho U\|^2$ in (\ref{inter-inequal}), we obtain the inequality \begin{equation} \label{gen-bound} \|\vecrho \G_k^\mu(u)\|^2\le \frac{\|\vecnu\|^2\|P\|_u^2-\nu_u^2P^2(\lambda)} {\|\vecnu\|^2 c_k^2\mu^2-2\nu_u P(\lambda) c_k\mu + \|P\|_u^2}. \end{equation} which, in the case $\mu=0$ $(k<\ecc)$, particularizes to $$ \|\vecrho \G_k^0 (u)\|^2 =\|\vecnu\|^2-\|\vecrho N_k(u)\|^2\le \|\vecnu\|^2-\nu_u^2\frac{P^2(\lambda)} { \|P\|_u^2}, $$ so that $$ \frac{P(\lambda)}{\|P\|_u}\le \frac{1}{\nu_u}\|\vecrho N_k(u)\| $$ and, when $\|P\|_u\le 1$, we get the bound (\ref{basic-inequal}) of Theorem \ref{basic-result}. Consequently, as stated in the hypotheses of the theorem, it suffices to study the case $\mu >0$. Furthermore, notice that the upper bound in (\ref{gen-bound}) is invariant under multiplication of $P$ by a constant, and when $\nu_uP(\lambda)=\|\vecnu\|^2c_k\mu$ such a bound takes the trivial value $\|\vecnu\|^2$. Thus, assuming $\nu_uP(\lambda)-\|\vecnu\|^2c_k\mu\neq 0$, we can choose, without loss of generality, the polynomial $P$ in such a way that $P(\lambda)=(1+\|\vecnu\|^2c_k\mu)/\nu_u$. In this case, (\ref{inter-inequal}) becomes \begin{equation} \label{inter-inequal-simpl} \frac{\|\vecnu\|^2}{\|\vecrho U\|^2}\ge \frac{1}{\|\vecnu\|^2\|P\|_u^2-\nu_u^2P^2(\lambda)} + 1, \end{equation} whence (\ref{gen-bound-2}) follows. Moreover, if such a bound is attained, then all the inequalities in the above proof must be equalities, whence we get two main consequences. First, (recall that now $\mu\neq 0$) we have $\|\vecrho U\|^2=\sum_{v\in U} \nu_v^2 =\sum_{v\in U} \nu_v$, so that $\nu_v=1$ for all $v\in U$, whence $\|\vecrho U\|^2=|\vecrho U|$. Second, we must have $\cos\{P\z,\z'\}=-1$, and therefore, using (\ref{normPz}), (\ref{normz'}), and the spectral decomposition of $\vecrho U$, we can compute $P\z$ in the following manner: \begin{eqnarray*} P\z & = & -\frac{\|P\z\|}{\|\z'\|}\z' =-\frac{\nu_u \sqrt{\|P\|_u^2-\frac{\nu_u^2 P^2(\lambda)}{\|\vecnu\|^2}}} {\sqrt{ |U|\left( 1-\frac{|U|}{\|\vecnu\|^2}\right) }} \left(\vecrho U-\frac{|U|}{\|\vecnu\|^2}\vecnu\right) \\ & = & \frac{-\nu_u}{\|\vecnu\|^2-|U|} \left( \vecrho U- \frac{|U|}{\|\vecnu\|^2}\vecnu \right) \end{eqnarray*} Using the above expression in the spectral decomposition of $P\vecrho u$, we get $$ P\vecrho u = \frac{\nu_u^2 P(\lambda)}{\|\vecnu\|^2}\vecnu +P\z =\frac{\nu_u^2 P(\lambda)}{\|\vecnu\|^2}\vecnu - \frac{\nu_u}{\|\vecnu\|^2-|U|} \left( \vecrho U- \frac{|U|}{\|\vecnu\|^2}\vecnu \right) $$ so that, denoting the multiplicative constants of $\vecnu$ and $\vecrho U$ by $\beta_k$ and $\gamma_k$, respectively, \begin{equation} \label{tight-more-gen} P\e_u = \beta_k\vecnu + \gamma_k\vecrho U = \frac{\nu_u P(\lambda)(\|\vecnu\|^2-|U|)+|U|} {\|\vecnu\|^2(\|\vecnu\|^2-|U|)}\vecnu - \frac{1}{\|\vecnu\|^2-|U|}\vecrho U. \end{equation} This gives (\ref{gen-tight}) when $k= \ecc$ (with $n_{\ecc}^\mu =|U|$) which, using the value of $\nu_uP(\lambda)$, can also be written as \begin{equation} \label{tight-more-gen-2} P\e_u = \beta_{\ecc}\vecnu + \gamma_{\ecc}\vecrho \G_\ecc^{\mu} (u) = \frac{1+ c_k\mu(\|\vecnu\|^2-n_{\ecc}^\mu)} {\|\vecnu\|^2-n_{\ecc}^\mu}\vecnu - \frac{1}{\|\vecnu\|^2-n_{\ecc}^\mu}\vecrho \G_\ecc^{\mu} (u). \end{equation} From this last expression, we get that if $v\in \G_\ecc^{\mu} (u)$, then $\nu_v=(\vecrho\G_\ecc^{\mu}(u))_v=1$ and $(P\e_u)_v=\beta_{\ecc}-\gamma_{\ecc}=c_k\mu$ (as it should be.) Otherwise, if $v\notin \G_\ecc^{\mu} (u)$, we have $(\vecrho\G_\ecc^{\mu} (u))_v=0$ and hence $(P\e_u)_v =\beta_{\ecc}\nu_v$. In particular, if $v\in \G_\ecc (u)\setminus \G_\ecc^{\mu} (u)$, it must be $(P\e_u)_v= c_k\mu_v$, where $\mu_v\ge 0$ is the number of $\ecc$-paths from $u$ to $v$. Thus, \begin{equation} \label{mu-v} \mu_v= \frac{\beta_\ecc}{c_k}\nu_v \end{equation} and such a number shows to be proportional to $\nu_v$. Let us now turn our attention to the case $k< \ecc$. Then, we clearly have $(P(\A))_{uv}=(P\e_u)_v=0$ for any vertex $v$ such that $\partial(u,v)\ge k$. Hence, we must have $\beta_k=0$ in (\ref{tight-more-gen}) and, therefore, $P\e_u=\gamma_k\vecrho U$. Furthermore, $(P(\A))_{uv}\neq 0$ for all $v\in \G_k(u) = V_k$, and therefore $U$ must be the whole set $V_k$, giving (\ref{restric-tight}). The value of $n_k^\mu=n_k$, given in (\ref{restric-equality}), is obtained from the equation $\beta_k=0$. Finally, condition (\ref{nu-ck-mu}) comes from equating such a value of $n_k$ to the upper bound in (\ref{gen-bound-2}). \endproof From the above proof, note that (\ref{gen-bound-2}) also applies when $\dgr P=d_u$, provided that $P(\mu_i)\neq 0$ for some $1\le i\le d_u$ (so that $\Phi>0$.) As in the case of Theorem \ref{basic-result}, the above theorem suggests studying the polynomials which achieve the best bound in (\ref{gen-bound-2}). Here, too, it turns out that the proper polynomials are of valuable help, as the next result shows. \begin{theo} \label{main-theo-pk} Let $u$ be a vertex of a graph $\G$, with local spectrum $\S_u (\G) =$ \linebreak $\{\lambda^{m_u(\lambda)}, \mu_1^{m_u(\mu_1)}, \ldots, \mu_{d_u}^{m_u(\mu_{d_u})}\}$, and positive eigenvector $\vecnu$, and let $p_k^u$, $0\le k\le d_u$, be the local proper polynomials. Let $a_k$ denote the leading coefficient of $p_k^u$, and consider the sum polynomials $q_k^u=\sum_{l=0}^k p_l^u$. For any given integers $\mu> 0$ and $0\le k< d_u$, consider the spectral weight $k$-excess $\Eb_k =\|\vecnu\|^2-\nu_u^2q_k^u(\lambda)$, and define $\Fb_k(\mu):=\nu_u a_k\mu-1$. Then, \begin{equation} \label{gen-opt-bound} \|\vecrho \G_k^\mu(u)\|^2\le \frac{p_k^u(\lambda)\Eb_k } {p_k^u(\lambda)\Fb_k(\mu)^2+a_k^2\mu^2\Eb_k}, \end{equation} and equality is attained if and only if $\|\vecrho \G_k^\mu(u)\|^2=n_k^\mu$, and either \begin{itemize} \item[(a)] when $k= \ecc$: \begin{equation} \label{pk-tight} P^*\e_u= \beta_\ecc^*\vecnu + \gamma_\ecc^*\vecrho\G_{\ecc}^\mu(u), \end{equation} with the polynomial \begin{equation} P^* := a_\ecc\mu\Eb_\ecc p_\ecc^u +p_\ecc^u(\lambda)\Fb_\ecc(\mu)\nu_u q_\ecc^u \end{equation} and constants \begin{equation} \beta_\ecc^* := p_\ecc^u(\lambda)\Fb_\ecc(\mu), \ \ \ \gamma_\ecc^* := p_\ecc^u(\lambda)\Fb_\ecc(\mu)^2+a_\ecc^2\mu^2\Eb_\ecc; \end{equation} \item[(b)] when $k< \ecc$: \begin{equation} \label{pk-restric-tight} p_k^u\e_u = \frac{1}{\nu_u}\vecrho V_k\, , \end{equation} in which case \begin{equation} \label{nk} n_k^\mu=n_k= \nu_u^2p_k^u(\lambda). \end{equation} \end{itemize} \end{theo} \proof Let us consider a generic polynomial $P=\sum_{l=0}^k \alpha_l p_l^u$, $\alpha_l\in \R$. Since $P$ must have leading coefficient $c_k=\alpha_k a_k$, we impose the condition $P(\lambda)=(1+ \alpha_k a_k n\mu)/\nu_u$, and hence \begin{eqnarray} \label{generic-P} P & = & \sum_{l=1}^{k} \alpha_l p_l^u + \frac{1+ \alpha_k a_k n\mu}{\nu_u} - \sum_{l=1}^{k} \alpha_l p_l^u(\lambda); \\ \label{norm-P} \|P \|_u^2 & = & \sum_{l=1}^{k} \alpha_l^2 p_l^u(\lambda) + \left(\frac{1+ \alpha_k a_k n\mu}{\nu_u} - \sum_{l=1}^{k} \alpha_l p_l^u(\lambda) \right)^2. \end{eqnarray} Therefore, looking at (\ref{inter-inequal-simpl}), our aim is to minimize the function $$ \Phi= \Phi(\alpha_1,\ldots\alpha_k) = \|\vecnu\|^2\|P\|^2_u-\nu_u^2P^2(\lambda) = \|\vecnu\|^2\|P\|_u^2 - (1+\|\vecnu\|^2\alpha_k a_k\mu)^2 $$ with $\|P\|_u^2$ given by (\ref{norm-P}) (remember that $\Phi$ is the square of a norm on the mesh $\M_u^\star$.) Then, the minimum is attained when \begin{eqnarray*} \alpha_1=\alpha_2=\cdots =\alpha_{k-1} & = & \frac{\nu_u p_k^u(\lambda)(1-\nu_u a_k\mu)} {\Delta}\, , \\ \alpha_k & = & \frac{\nu_u p_k^u(\lambda) - a_k\mu(\|\vecnu\|^2 - \nu_u^2 q_{k-1}^u(\lambda))} {\Delta}\, , \end{eqnarray*} where $$ \Delta = \nu_u^2q_{k-1}^u(\lambda)(p_k^u(\lambda)-a_k^2\mu^2\|\vecnu\|^2) + (\nu_u p_k^u(\lambda)-a_k\mu\|\vecnu\|^2)^2 $$ or, using $q_{k-1}^u(\lambda)=q_k^u(\lambda)-p_k^u(\lambda)$ and the definitions of $\Eb_k$ and $\Fb_k(\mu)$, \begin{eqnarray*} \alpha_1=\alpha_2=\cdots =\alpha_{k-1} & = & -\frac{\nu_u p_k^u(\lambda)\Fb_k(\mu)} {\Delta}\, , \\ \alpha_k & = & \frac{\nu_u p_k^u(\lambda) - a_k\mu\Eb_k} {\Delta}\, , \end{eqnarray*} with $$ \Delta= (\|\vecnu\|^2a_k^2\mu^2- p_k^u(\lambda)) \Eb_k+\|\vecnu\|^2p_k^u(\lambda)\Fb_k(\mu)^2. $$ Then, such a minimum turns out to be $$ \Phi_{\min} = \frac{p_k^u(\lambda)\Eb_k}{\Delta} $$ and, according to (\ref{gen-bound-2}), the upper bound in (\ref{gen-opt-bound}) comes from $\|\vecnu\|^2\frac{\Phi_{\min}}{1+\Phi_{\min}}$. This bound corresponds to using in (\ref{gen-bound}) the polynomial (\ref{generic-P}) with the above values of the coefficients $\alpha_l$, $1\le l\le k$. Namely, \begin{equation} P=-\frac{1}{\Delta}\left( a_k\mu \Eb_k p_k^u +\nu_u p_k^u(\lambda)\Fb_k(\mu) q_k^u \right). \end{equation} When the equality is attained, we can use the values of $P(\lambda)$ and $n_k^\mu=|\G_k^\mu (u)|$ to compute the multiplicative constants of $\vecnu$ and $\vecrho\G_k^ \ecc(u)$ in (\ref{tight-more-gen}), which turn out to be $$ \beta_k=-\frac{1}{\Delta}p_k^u(\lambda)\Fb_k(\mu) \mbox{\ \ \ and \ \ \ } \gamma_k=-\frac{1}{\Delta}\left( p_k^u(\lambda)\Fb_k(\mu)^2+a_k^2\mu^2\Eb_k \right) $$ respectively, thus giving \begin{equation} \label{pk-tight-gen} P^*\e_u=\beta_k^*\vecnu+\gamma_k^*\vecrho\G_k^\mu (u) \end{equation} with $P^*=-\Delta P$, $\beta_k^*=-\Delta \beta_k$ and $\gamma_k^*=-\Delta \gamma_k$. Now, from these facts we can reason as in Theorem \ref{main-theo} to obtain the claimed results for the cases $k=\ecc$ and $k<\ecc$. Thus, in the former case, (\ref{pk-tight-gen}) becomes (\ref{pk-tight}) and, if $v\in \G_\ecc (u)\setminus \G_\ecc^{\mu} (u)$, the number $\mu_v$ of $\ecc$-paths from $u$ to $v$ is obtained from \begin{equation} \label{mu-v-pk} \nu_v \beta_\ecc^*= \nu_v p_\ecc^u(\lambda)\Fb_\ecc(\mu) =c_\ecc^* \mu_v, \end{equation} where $c_\ecc^*$ stands here for the leading coefficient of $P^*$, that is $$ c_\ecc^*=a_\ecc\left( a_\ecc\mu \Eb_\ecc +\nu_u p_\ecc^u(\lambda)\Fb_\ecc(\mu) \right). $$ Finally, in the case $k<\ecc$, the only real solution obtained when we solve Eq. (\ref{nu-ck-mu}) for $\mu$ turns out to be $\mu=\frac{1}{a_k\nu}$, and hence $\Fb_k(\mu)=0$. (More simply, the same conclusions are reached from the equation $\beta_k^*=0$.) Substituting these values into (\ref{pk-tight-gen}) and the bound in (\ref{gen-opt-bound}) we get (\ref{pk-restric-tight}) and (\ref{nk}), respectively, in concordance with (\ref{loc-dist-pol}). \endproof Notice that, as in the case of Theorem \ref{main-theo}, the bound (\ref{gen-opt-bound}) also applies when $\mu=0$, giving $\|\vecrho \G_k^{0} (u)\|^2=e_k^\star (u)\le \Eb_k$, in concordance with (\ref{Eb_k}). If $\G$ is regular, the above results take a more simple form since, from $\vecnu=\j$, we have $\|\vecnu\|^2=n$ and $\|\vecrho \G_k^\mu(u)\|^2=n_k^\mu$. Moreover, when the corresponding bound (\ref{gen-opt-bound}) is attained for $k=\ecc$, the value of $\mu_v$ in (\ref{mu-v-pk}) becomes a constant, say $\mubar$, for every vertex $v\in \G_\ecc(u)\setminus \G_\ecc^{\mu}(u)$. Namely, \begin{equation} \label{mu-bar} \mubar=\frac{\beta_{\ecc}^*}{c_\ecc^*}=\frac{p_\ecc^u(\lambda)\Fb_\ecc(\mu)} {a_\ecc p_\ecc^u(\lambda)\Fb_\ecc(\mu)+ a_\ecc^2\mu\Eb_\ecc}. \end{equation} Consequently, we get the partition $\G_{\ecc}(u)=\G_{\ecc}^\mu (u)\cup \G_{\ecc}^{\mubar}(u)$. In this case, a more compact way of giving the above relation between $\mu$ and $\mubar$ is $$ p_\ecc^u(\lambda)\Fb_\ecc(\mu)\Fb_\ecc(\mubar) = \Eb_\ecc a_\ecc^2\mu\mubar\, , $$ showing the symmetry between both parameters. Notice that, in particular, it might be $\mu'=0$, in which case $\beta_{\ecc}^*=p_\ecc^u(\lambda)\sigma_\ecc (\mu)=0$, and we would get the same consequences as in the case $k<\ecc$. The two following corollaries are straightforward consequences of Theorem \ref{main-theo-pk}. \begin{coro} Let $u$ be a vertex of a graph $\G$, with eccentricity $\ecc (u)$ and local proper polynomials $p_k^u$. Then, for $k< d_u$, \begin{itemize} \item[(a)] \ds \|\vecrho \G_k(u)\|^2\le p_k^u(\lambda)\Eb_k\sum_{\mu\ge 1}\frac{1} {p_k^u(\lambda)\Fb_k(\mu)^2+a_k^2\mu^2\Eb_k}$; \item[(b)] \ds \min_{\mu\ge 1} \{p_k^u(\lambda)\Fb_k(\mu)^2+a_k^2\mu^2\Eb_k \} > p_k^u(\lambda)\Eb_k \ \ \Rightarrow \ \ \ecc (u) < k$. \end{itemize} \end{coro} \proof (a) is a direct consequence of the theorem and $\|\vecrho \G_k(u)\|^2=\sum_{\mu\ge 1}\|\vecrho \G_k^\mu (u)\|^2$. To prove (b) notice that, from $n_k^\mu\le \|\G_k^\mu (u)\|^2$ and the given condition, we get $$ n_k^\mu \le \left\lfloor \frac{p_k^u(\lambda)\Eb_k } {p_k^u(\lambda)\Fb_k(\mu)^2+a_k^2\mu^2\Eb_k}\right\rfloor < 1 $$ for any $\mu\ge 1$. Thus, $n_k=0$ and the result follows. \endproof \begin{coro} Let $u$ be a vertex of a graph $\G$, with eccentricity $\ecc (u)=\ecc$, and local proper polynomial $p_k^u$ with degree $k<\ecc$ and leading coefficient $a_k$. Then, (\ref{pk-restric-tight}) holds, that is $p_k^u\e_u = \frac{1}{\nu_u}\vecrho V_k$, with $\|\vecrho V_k\|^2=|V_k|$, if and only if the quotient $1/\nu_u a_k$ is an integer, say $\mu$, and the number $n_k=|V_k|$ of vertices at distance $k$ from $u$ is given by (\ref{nk}): $n_k=n_k^\mu= \nu_u^2 p_k^u(\lambda)$. \end{coro} \proof Assuming that (\ref{pk-restric-tight}) holds and $\|\vecrho V_k\|^2=|V_k|$, we have $$ \nu_u p_k^u(\lambda)=\langle \e_u, p_k^u(\lambda)\vecnu \rangle=\langle p_k^u\e_u, \vecnu \rangle =\frac{1}{\nu_u}\langle \vecrho V_k, \vecnu \rangle=\frac{1}{\nu_u}\|\vecrho V_k\|^2=\frac{n_k}{\nu_u} $$ and, for any vertex $v\in V_k$, $$ (\A^k)_{uv}=\langle \A_k\e_u, \e_v \rangle = \frac{1}{a_k}\langle p_k^u\e_u, \e_v \rangle =\frac{1}{a_k \nu_u}\langle \vecrho V_k, \e_v \rangle=\frac{1}{a_k \nu_u}. $$ Hence, $n_k$ is given by (\ref{nk}), and $1/a_k\nu_u$ is an integer. Conversely, if such is the case, then the upper bound in (\ref{gen-opt-bound}) for $\mu=1/\nu_va_k$ becomes $\nu_u^2 p_k^u(\lambda)$, and Theorem \ref{main-theo-pk} ($k<\ecc$) applies. \endproof When the considered graph is partially walk-regular, and the equality is attained for all vertices, the results of Theorem \ref{main-theo-pk} look much better, as it is shown next. \begin{theo} \label{special-bounds-spec-reg} Let $\G=(V,E)$ be a $\tau$-partially walk-regular graph on $n$ vertices, with adjacency matrix $\A$ and spectrum $\S(\G)=\{\lambda,\lambda_1^{m_1},\ldots,\lambda_d^{m_d}\}$. Let $p_k$ be the proper polynomial with degree $k\le \lfloor \frac{\tau}{2}\rfloor$ if $\tau p_k (\lambda)\Eb_k \ \ \Rightarrow \ \ D(\G) < k$. \ \ \ $\Box$ \end{itemize} \end{coro} \begin{coro} Let $\G$ be a $\tau$-partially walk-regular graph as above. Let $k\le \lfloor\frac{\tau}{2}\rfloor$ if $\tau