Graph Spectrum

The graph spectrum of a graph is the multiset of graph eigenvalues of its adjacency matrix. (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 connected 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).

The product over the spectrum of a graph on vertices, counting each graph eigenvalue with its multiplicity, is its characteristic polynomial in the monic convention. In the convention used here and by the Wolfram Language, the characteristic polynomial of its adjacency matrix is (Wolfram Research).

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 Eigenvalues[AdjacencyMatrix[g]]. Precomputed spectra for many named graphs can be obtained using GraphData[graph, "Spectrum"].

A graph whose spectrum consists entirely of integers is known as an integral graph.

The maximum vertex degree of a connected graph is an eigenvalue of iff 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 to generate a thousand conjectures in spectral graph theory (DeLaVina 2005, Roucairol and Cazenave 2024).