Equivalent characterizations of the spectra of graphs and applications to measures of distance-regularity

Abstract

As it is well known, the spectrum $\mathrm{sp}\Gamma$ (of the adjacency matrix $A$) of a graph $\Gamma$, with $d$ distinct eigenvalues other than its spectral radius ${\lambda }_0$, usually provides a lot of information about the structure of $G$. Moreover, from $\mathrm{sp}\Gamma$ we can define the so-called predistance polynomials $p_0,\dots ,p_d\in {\mathbb{R}}_d[x]$, with $\mathrm{dgr}{p}_i=i$, $i=0,\dots ,d$, which are orthogonal with respect to the scalar product $⟨f,g{⟩}_{\Gamma }=\frac{1}{n}\mathrm{tr}(f(A)g(A))$ and normalized in such a way that $\Vert p_i{\Vert }_{\Gamma }^2=p_i({\lambda }_0)$. They can be seen as a generalization for any graph of the distance polynomials of a distance-regular graph. Going further, we consider the preintersection numbers ${\xi }_{ij}^h$ for $i,j,h\in \{0,\dots ,d\}$, which generalize the intersection numbers of a distance-regular graph, and they are the Fourier coefficients of $p_i{p}_j$ in terms of the basis $\{p_h{\}}_{0\le h\le d}$. The aim of this paper is to show that, for any graph $\Gamma$, the information contained in its spectrum, predistance polynomials, and preintersection numbers is equivalent. Also, we give some characterizations of distance-regularity which are based on the above concepts. For instance, we comment upon the so-called spectral excess theorem stating that a connected regular graph $G$ is distance-regular if and only if its spectral excess, which is the value of $p_d$ at ${\lambda }_0$, equals the average excess, that is, the mean of the numbers of vertices at extremal distance $d$ from every vertex.

References in corpus (1)

• On almost distance-regular graphs