Equivalent characterizations of the spectra of graphs and some applications
Author
Diego, V.; Fàbrega, J.; Fiol, M.
Type of activity
Presentation of work at congresses
Name of edition
International Workshop on Combinatorial and Computational Aspects of Optimization, Topology and Algebra
Date of publication
2016
Presentation's date
2016-12-01
Book of congress proceedings
International Workshop on Combinatorial and Computational Aspects of Optimization, Topology and Algebra (ACCOTA 2016): Los Cabos, Baja California, Mexico: November 27 to December 3, 2016
As it is well known, the spectrum sp G (of the adjacency matrix A) of a graph G, with d distinct eigenvalues other than its spectral radius ¿0, usually provides a lot of information about the structure of G. Moreover, from sp G we can define the so-called predistance polynomials p0, . . . , pd ¿ Rd[x], with dgr pi = i, i = 0, . . . , d, which are orthogonal with respect to the scalar product hf, giG = 1 n tr(f(A)g(A)) and normalized in such a way that kpik 2 G = pi(¿0). They can be seen as a ...
As it is well known, the spectrum sp G (of the adjacency matrix A) of a graph G, with d distinct eigenvalues other than its spectral radius ¿0, usually provides a lot of information about the structure of G. Moreover, from sp G we can define the so-called predistance polynomials p0, . . . , pd ¿ Rd[x], with dgr pi = i, i = 0, . . . , d, which are orthogonal with respect to the scalar product hf, giG = 1 n tr(f(A)g(A)) and normalized in such a way that kpik 2 G = 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 ¿ h ij 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 G, 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.