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.