### On a version of the spectral excess theorem

#### Abstract

Given a regular (connected) graph *G*=(*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

*G*and the arithmetic (or harmonic) mean of the numbers of vertices at distance at most

*D*-1 from every vertex. The same result 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.

#### Keywords

#### Full Text:

PDFDOI: http://dx.doi.org/10.5614/ejgta.2020.8.2.15

#### References

N. Biggs, Algebraic Graph Theory, Cambridge University Press, Cambridge, 1974, second edition, 1993.

A.E. Brouwer and W.H. Haemers, Spectra of Graphs, Springer, 2012; available online at http://homepages.cwi.nl/aeb/math/ipm/.

M. Camara, J. Fabrega, M.A. Fiol, E. Garriga, Some families of orthogonal polynomials of a discrete variable and their applications to graphs and codes, Electronic J. Combinatorics 16 (2009), #R83

E.R. van Dam, The spectral excess theorem for distance-regular graphs: a global (over)view, Electronic J. Combinatorics 15 (2008), #R129.

E.R. van Dam and M.A. Fiol, The Laplacian spectral excess theorem for distance-regular graphs, Linear Algebra Appl. 458 (2014) 245–250.

A.J. Hoffman, On the polynomial of a graph, Amer. Math. Monthly 70 (1963) 30–36.

M.A. Fiol, Algebraic characterizations of distance-regular graphs, Discrete Math. 246 (2002) 111–129.

M.A. Fiol, Quotient polynomial graphs, Linear Algebra Appl. 488 (2016), 363–376.

M.A. Fiol, S. Gago, E. Garriga, A simple proof of the spectral excess theorem for distance- regular graphs, Linear Algebra Appl. 432 (2010) 2418–2422.

M.A. Fiol, E. Garriga, and J.L.A. Yebra, Locally pseudo-distance-regular graphs, J. Combin. Theory Ser. B 68 (1996) 179–205.

M.A. Fiol, E. Garriga, From local adjacency polynomials to locally pseudo-distance-regular graphs, J. Combin. Theory Ser. B 71 (1997) 162–183.

A.J. Hoffman, On the polynomial of a graph, Amer. Math. Monthly 70 (1963) 30–36.

P. Weichsel, On distance-regularity in graphs, J. Combin. Theory Ser. B 32 (1982) 156–161.

### Refbacks

- There are currently no refbacks.

ISSN: 2338-2287

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.