Equivalent characterizations of the spectra of graphs and applications to measures of distance-regularity

MaRDI QIDQ5124690zbMATH OpenFDO

Authors Víctor Diego, J. Fàbrega, Miquel Angel Fiol

Publication date 30 September 2020

Full work available at URL https://arxiv.org/abs/1608.00091, https://journals.uwyo.edu/index.php/ela/article/view/5061

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

distance-regular graphgraph spectrumspectral excess theorempredistance polynomialspreintersection numbers

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Association schemes, strongly regular graphs (05E30) Distance in graphs (05C12)

Abstract: As it is well known, the spectrum $msp,Gamma$ (of the adjacency matrix $A$) of a graph $Gamma$, with $d$ distinct eigenvalues other than its spectral radius $lambd{a}_0$, usually provides a lot of information about the structure of $G$. Moreover, from $msp,Gamma$ we can define the so-called predistance polynomials $p_0,ldots,p_{d}in{mathbbR}_d[x]$, with $mdgr,p_i=i$, $i=0,ldots,d$, which are orthogonal with respect to the scalar product $langlef,gangl{e}_{Gamma}=frac1nmtr,(f(A)g(A))$ and normalized in such a way that $|p_i{|}_{Gamma}^2=p_i(lambd{a}_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 $x{i}_{ij}^h$ for $i,j,hin0,ldots,d$, which generalize the intersection numbers of a distance-regular graph, and they are the Fourier coefficients of $p_i{p}_j$ in terms of the basis ${p_h}_{0lehled}$. The aim of this paper is to show that, for any graph $Gamma$, 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 $p_d$ at $lambd{a}_0$, equals the average excess, that is, the mean of the numbers of vertices at extremal distance $d$ from every vertex.

Recommendations

• On a version of the spectral excess theorem
• Some spectral and quasi-spectral characterizations of distance-regular graphs
• On some approaches to the spectral excess theorem for nonregular graphs
• The spectral excess theorem for distance-regular graphs: a global (over)view
• The Laplacian spectral excess theorem for distance-regular graphs

Cites work

• scientific article; zbMATH DE number 428989 (Why is no real title available?)
• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 1028230 (Why is no real title available?)
• scientific article; zbMATH DE number 3445271 (Why is no real title available?)
• A new family of distance-regular graphs with unbounded diameter
• A short proof of the odd-girth theorem
• A simple proof of the spectral excess theorem for distance-regular graphs
• A spectral equivalent condition of the \(P\)-polynomial property for association schemes
• A spectral excess theorem for nonregular graphs
• Algebraic characterizations of distance-regular graphs
• An eigenvalue characterization of antipodal distance-regular graphs
• An odd characterization of the generalized odd graphs
• Characterizing \((\ell ,m)\)-walk-regular graphs
• Distance-regular graphs
• From local adjacency polynomials to locally pseudo-distance-regular graphs
• On almost distance-regular graphs
• On the Polynomial of a Graph
• Some families of orthogonal polynomials of a discrete variable and their applications to graphs and codes
• Some spectral and quasi-spectral characterizations of distance-regular graphs
• Spectra of graphs
• Spectral characterizations of some distance-regular graphs
• The Gewirtz graph: An exercise in the theory of graph spectra
• The spectral excess theorem for distance-regular graphs: a global (over)view

Cited in

(5)

• A quasi-spectral characterization of strongly distance-regular graphs
• Spectral bounds and distance-regularity
• On a version of the spectral excess theorem
• Some spectral and quasi-spectral characterizations of distance-regular graphs
• The spectral excess theorem for graphs with few eigenvalues whose distance-2 or distance-1-or-2 graph is strongly regular

This page was built for publication: Equivalent characterizations of the spectra of graphs and applications to measures of distance-regularity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5124690)