Some Applications of the Proper and Adjacency Polynomials in the Theory of Graph Spectra

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 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\geq 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.