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  with -fold degenerate eigenvalues  is commonly denoted  (van Dam and Haemers 2003) or  (Biggs 1993, p. 8; Buekenhout and Parker 1998).

The product  over the elements of the spectrum of a graph  is known as the characteristic polynomial of , and is given by the characteristic polynomial of the adjacency matrix of  with respect to the variable .

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).

---

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 ." 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.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.

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.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength