Abstract:

Given a vertex $u\inV$ of a graph $\Gamma=(V,E)$, the (local) proper polynomials constitute a sequence of orthogonal polynomials, constructed from the socalled $u$local spectrum of $\Gamma$. These polynomials can be thought of as a generalization, for all graphs, of the distance polynomials for te distanceregular graphs. The (local) adjacency polynomials, which are basically sums of proper polynomials, were recently used to study a new concept of distanceregularity for nonregular graphs, and also to give bounds on some distancerelated 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, distanceregular graphs are characterized from their spectra 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 $\Gamma$ and the weight $k$excess of a vertex. Given the integers $k,\mu\ge 0$, let $\Gamma_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 each of such vertices. As a main result, an upper bound for the cardinality of $\Gamma_k^{\mu}(u)$ is derived, showing that $\Gamma_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 distane three from every vertex of a regular graph with four distinct eigenvaluessetting $k=2$ and $\mu=0$and, more generally, the number of nonadjacent vertices to every vertex $u\in V$, which have $\mu$ common neighbours with it. 