TOPICS
Search

Determined by Spectrum


GraphSpectrum

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 C_4 union K_1 and star graph S_5, illustrated above, both have spectrum (-2,0,0,0,2) (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 n=1 to 12 vertices can be summarized in the following table (Wang and Wang 2024), which follows from the results of Brouwer and Spence (2009).

n# graphs# DS graphsfraction DS graphs
OEISA000088A178925
111100%
222100%
344100%
41111100%
5343294.1%
615614693.6%
7104493489.5%
8123461062486.1%
927466822362981.4%
1012005168944456278.7%
11101899786480366618878.9%
1216509117259213402360011181.2%

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

The numbers of simple graphs on n=1, 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 K_n, regular complete bipartite graphs K_(n,n), cycle graphs, triangular graphs for n!=8, and the rook graphs L_k for k!=4 (Haemers 2006). In addition, the Coxeter graph, Biggs-Smith graph, collinearity graphs of the generalized octagons of orders (2,1), (3,1), and (4,1), the generalized dodecagon (2,1), 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 Ci_(5k)(1,4,6,9,11,14,...,|_5k/2_|), which is C_5 tensor J_k, where J_k is the k×k unit matrix,  tensor 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 L_4 and Shrikhande graph, tesseract graph Q_4 and Hoffman graph, triangular graph T_8 and Chang graphs, and the 25- and 26-Paulus graphs.


See also

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

Explore with Wolfram|Alpha

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

Subject classifications