TOPICS

# Determined by Spectrum

Two nonisomorphic graphs can share the same graph spectrum, i.e., have the same eigenvalues of their adjacency matrices. Such graphs are called cospectral. For example, the graph union and star graph , illustrated above, both have spectrum (Skiena 1990, p. 85). This is the smallest pair of simple graphs that are cospectral.

A graph that is not cospectral with any other graph is said to be "determined by spectrum," or DS for short. Determining which graphs are uniquely determined by their spectra is in general a very hard problem. Only a small fraction of graphs are known to be so determined, but as conjectured by van Dam and Haemers (van Dam and Haemers 2002, Haemers 2016), it is conceivable that almost all graphs have this property. This assertion is sometimes known as the Haemers conjecture.

The numbers of simple graphs and DS graphs together with the fraction of DS graphs on to 12 vertices can be summarized in the following table (Wang and Wang 2024), which follows from the results of Brouwer and Spence (2009).

 # graphs # DS graphs fraction DS graphs OEIS A000088 A178925 1 1 1 100% 2 2 2 100% 3 4 4 100% 4 11 11 100% 5 34 32 94.1% 6 156 146 93.6% 7 1044 934 89.5% 8 12346 10624 86.1% 9 274668 223629 81.4% 10 12005168 9444562 78.7% 11 1018997864 803666188 78.9% 12 165091172592 134023600111 81.2%

In the Wolfram Language, graphs known to be determined by their spectra are identified as GraphData["DeterminedBySpectrum"].

The numbers of simple graphs on , 2, ... nodes that are determined by spectrum are 1, 2, 4, 11, 32, 146, 934, 10624, 223629, ... (OEIS A178925), while the corresponding numbers not determined by spectrum are 0, 0, 0, 0, 2, 10, 110, 1722, 51039, 2560606, ... (OEIS A06608).

Graphs that are known to be uniquely determined by their spectra include complete graphs , regular complete bipartite graphs , cycle graphs, triangular graphs for , and the rook graphs for (Haemers 2006). In addition, the Coxeter graph, Biggs-Smith graph, collinearity graphs of the generalized octagons of orders , , and , the generalized dodecagon , the M22 graph, and the coset graphs of the doubly truncated binary Golay code and the extended ternary Golay code are determined by their spectra (van Dam and Haemers 2003b).

The complement of a distance-regular graph that is determined by its spectrum is also determined by its spectrum (van Dam and Haemers 2003b). The disjoint union of multiple copies of a strongly regular determined-by-spectrum graph is also determined by spectrum (van Dam and Haemers 2003b).

An infinite family of determined-by-spectrum graphs is given by , which is , where is the unit matrix, denotes the Kronecker product of adjacency matrices (van Dam and Haemers 2003b), and 1, 4, 6, 9, 11, ... (OEIS A047209) is the sequence of positive integers that are congruent to 1 and 4 (mod 5).

Graphs that are not determined by their spectra include the rook graph and Shrikhande graph, tesseract graph and Hoffman graph, triangular graph and Chang graphs, and the 25- and 26-Paulus graphs.

Chang Graphs, Cospectral Graphs, Graph Isomorphism, Graph Spectrum, Hoffman Graph, Shrikhande Graph

## Explore with Wolfram|Alpha

More things to try:

## References

Brouwer, A. E. and Spence, E. "Cospectral Graphs on 12 Vertices." Elect. J. Combin., Vol. 16, No. 1, 2009. https://doi.org/10.37236/258.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.Haemers, W. H. "Are Almost All Graphs Determined by Their Spectrum?" Not. S. Afr. Math. Soc. 47, 42-45, 2016.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.Sloane, N. J. A. Sequences AA06608/M1981, A047209, and A178925 in "The On-Line Encyclopedia of Integer Sequences."van Dam, E. R. and Haemers, W. H. "Spectral Characterizations of Some Distance-Regular Graphs." J. Algebraic Combin. 15, 189-202, 2003a.van Dam, E. R. and Haemers, W. H. "Which Graphs Are Determined by Their Spectrum?" Lin. Algebra Appl. 373, 139-162, 2003b.Wang, W. and Wang, W. "Haemers' Conjecture: An Algorithmic Perspective." Experimental Math., 10 Apr 2024.

## Cite this as:

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