2016/07/30 by Víctor Diego, Diego, V., J. Fàbrega +3
Computer Science · Mathematics · #05C50 #05E30 #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #Matrix Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.1608.00091
openalex publication_date 2016/07/30 · openalex created_date 2016/08/23 · openalex updated_date 2026/08/01
As it is well known, the spectrum \rm sp Γ (of the adjacency matrix A) of a graph Γ, with d distinct eigenvalues other than its spectral radius λ0, usually provides a lot of information about the structure of G. Moreover, from \rm sp Γ we can define the so-called predistance polynomials p0,…,pd∈ \mathbb Rd[x], with \rm dgr pi=i, i=0,…,d, which are orthogonal with respect to the scalar product ⟨ f, g⟩Γ =(1)/(n)\rm tr (f(A)g(A)) and normalized in such a way that ‖pi‖Γ2=pi(λ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 ξijh for i,j,h∈\0,…,d\, which generalize the intersection numbers of a distance-regular graph, and they are the Fourier coefficients of pipj in terms of the basis \ph\0≤ h≤ d. The aim of this paper is to show that, for any graph Γ, 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 pd at λ0, equals the average excess, that is, the mean of the numbers of vertices at extremal distance d from every vertex.