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 with -fold degenerate eigenvalues is commonly denoted (van Dam and Haemers
2003) or
(Biggs 1993, p. 8; Buekenhout and Parker 1998).
The notation
is also used for graph eigenvalues (e.g., Godsil
and Royle 2001, p. 193), though sometimes with an indexing convention starting
with
being the smallest (instead of ). A graph with diameter has a spectrum consisting of at least
distinct eigenvalues, with the bound
becoming tight for a distance-regular graph,
which has exactly
distinct eigenvalues (Fallat et al. 2024).
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).
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 ." 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 Science69,
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.