On a version of the spectral excess theorem

2019/06/04 by M.A. Fiol, Fiol, M. A., Safet Penjić +1
Computer Science · Mathematics · #05C50 #05E30 #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #Matrix Theory and Algorithms

paper · doi:10.48550/arxiv.1906.01307

openalex publication_date 2019/06/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a regular (connected) graph Γ=(X,E) with adjacency matrix A, d+1 distinct eigenvalues, and diameter D, we give a characterization of when its distance matrix A_D is a polynomial in A, in terms of the adjacency spectrum of Γ and the arithmetic (or harmonic) mean of the numbers of vertices at distance ≤ D-1 of every vertex. The same results is proved for any graph by using its Laplacian matrix L and corresponding spectrum. When D=d we reobtain the spectral excess theorem characterizing distance-regular graphs.

Related

• The spectral excess theorem for graphs with few eigenvalues whose distance-2 or distance-1-or-2 graph is strongly regular
• On some approaches to the spectral excess theorem for nonregular graphs
• Equivalent characterizations of the spectra of graphs and applications to measures of distance-regularity
• The spectral excess theorem for distance-regular graphs having distance-d graph with fewer distinct eigenvalues
• Algebraic characterizations of regularity properties in bipartite graphs