Graph Spectrum
The set of graph eigenvalues of the adjacency matrix is called the spectrum of the graph. (But note that in physics, the eigenvalues
of the Laplacian matrix of a graph are sometimes
known as the graph's spectrum.) The spectrum of a graph 👁 G
with 👁 n_i
-fold degenerate eigenvalues 👁 lambda_i
is commonly denoted 👁 Spec(G)=(lambda_1)^(n_1)(lambda_2)^(n_2)...
(van Dam and Haemers
2003) or 👁 (lambda_1 lambda_2 ...; n_1 n_2 ...)
(Biggs 1993, p. 8; Buekenhout and Parker 1998).
The notation 👁 theta_i
is also used for graph eigenvalues (e.g., Godsil
and Royle 2001, p. 193), though sometimes with an indexing convention starting
with 👁 theta_0
being the smallest (instead of 👁 lambda_1
). A graph with diameter 👁 d
has a spectrum consisting of at least
👁 d+1
distinct eigenvalues, with the bound
becoming tight for a distance-regular graph,
which has exactly 👁 d+1
distinct eigenvalues (Fallat et al. 2024).
The product 👁 product_(k)(x-s_k)
over the elements of the spectrum of a graph 👁 G
is known as the characteristic
polynomial of 👁 G
,
and is given by the characteristic polynomial
of the adjacency matrix of 👁 G
with respect to the variable 👁 x
.
The largest absolute value of a graph's spectrum is known as its spectral radius.
The spectrum of a graph may be computed in the Wolfram Language using [[g]]. Precomputed spectra for many named graphs can be obtained using [graph, ].
A graph whose spectrum consists entirely of integers is known as an integral graph.
The maximum vertex degree of a connected graph 👁 G
is an eigenvalue of 👁 G
iff 👁 G
is a regular graph.
Two nonisomorphic graphs can share the same spectrum. Such graphs are called cospectral. There seems to be no standard name for graphs known to be uniquely determined by their spectra. While they could conceivably be called spectrally unique, the term "determined by spectrum" has been used in practice (van Dam and Haemers 2003).
A software package known as Graffiti, written in the mid-1980s by Siemion Fajtlowicz, has been used generate a thousand conjectures in spectral graph theory (DeLaVina 2005, Roucairol and Cazenave 2024).
See also
Algebraic Connectivity, Determined by Spectrum, Characteristic Polynomial, Cospectral Graphs, Graph Eigenvalue, Graph Energy, Integral Graph, Laplacian Matrix, Spectral RadiusExplore with Wolfram|Alpha
More things to try:
References
Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, 1993.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Theorem 3.1.1 in Distance-Regular Graphs. New York: Springer-Verlag, 1989.Buekenhout, F. and Parker, M. "The Number of Nets of the Regular Convex Polytopes in Dimension 👁 <=4
." Disc. Math. 186, 69-94, 1998.Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.DeLaVina, E. "On Some History of the Development of Graffiti." It Graphs and Discovery DIMACS: Series in Discrete Mathematics and Theoretical Computer Science 69, 81-118.2005.Fallat, S.; Gupta, H.; Herman, A.; and Parenteau, J. "Minimum Number of Distinct Eigenvalues of Distance-Regular and Signed Johnson Graphs." 31 Oct 2024. https://arxiv.org/abs/2411.00250.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, 2001.Haemers, W. H. "Spectral Characterization of Graphs." In IPM Combinatorics II: Design Theory, Graph Theory, and Computational Methods. April 22-27, 2006, IPM, Tehran. http://www.ipm.ac.ir/combinatoricsII/abstracts/Haemers1.pdf.Roucairol, M. and Cazenave, T. "Refutation of Spectral Graph Theory Conjectures with Search Algorithms." 27 Sep 2024. https://arxiv.org/abs/2409.18626.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 85, 1990.van Dam, E. R. and Haemers, W. H. "Spectral Characterizations of Some Distance-Regular Graphs." J. Algebraic Combin. 15, 189-202, 2003.Wilf, H. "Graphs and Their Spectra: Old and New Results." Congr. Numer. 50, 37-43, 1985.
Referenced on Wolfram|Alpha
Graph SpectrumCite this as:
Weisstein, Eric W. "Graph Spectrum." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GraphSpectrum.html