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

zbMATH Open1448.05127arXiv1608.00091MaRDI QIDQ5124690FDOQ5124690

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

Publication date: 30 September 2020

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.

Full work available at URL: https://arxiv.org/abs/1608.00091

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

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

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)

Cites Work

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

Cited In (5)

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

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)