On a version of the spectral excess theorem

Miquel Àngel Fiol, Safet Penjic

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 AD 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


graph, adjacency algebra, spectrum, harmonic mean, distance-regular graph, Laplacian

Full Text:

PDF

DOI: 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

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

View EJGTA Stats