TOPICS
Search

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 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 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 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 Radius

Explore with Wolfram|Alpha

References

Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, 1993.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.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 Spectrum

Cite this as:

Weisstein, Eric W. "Graph Spectrum." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GraphSpectrum.html

Subject classifications