Cospectral graphs, also called isospectral graphs, are graphs that share the same graph spectrum. The smallest pair of isospectral graphs is the graph union and star graph , illustrated above, both of which have graph spectrum (Skiena 1990, p. 85). The first example was found by Collatz and Sinogowitz (1957) (Biggs 1993, p. 12). Many examples are given in Cvetkovic et al. (1998, pp. 156-161) and Rücker et al. (2002). The smallest pair of cospectral graphs is the graph union and star graph , illustrated above, both of which have graph spectrum (Skiena 1990, p. 85).
The following table summarizes some prominent named cospectral graphs.
cospectral graphs | |
12 | 6-antiprism graph, quartic vertex-transitive graph Qt19 |
16 | Hoffman graph, tesseract graph |
16 | (4,4)-rook graph, Shrikhande graph |
25 | 25-Paulus graphs |
26 | 26-Paulus graphs |
28 | Chang graphs, 8-triangular graph |
70 | Harries graph, Harries-Wong graph |
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 it is conceivable that almost all graphs have this property (van Dam and Haemers 2003, Haemers 2016), an assertion sometimes known as the Haemers conjecture.
Brouwer and Spence (2009) determined the numbers of cospectral simple graphs on nodes up to , giving 0, 0, 0, 0, 2, 10, 110, 1722, 51039, 2560606, 215331676, 3106757248, ... (OEIS A006608) for , 2, .... The numbers of pairs of isospectral simple graphs (excluding pairs that are parts of triples, etc.) are 0, 0, 0, 0, 1, 5, 52, 771, 21025, ... (OEIS A099881). Similarly, the numbers of triples of isospectral graphs (excluding triples that are parts of quadruples, etc.) are 0, 0, 0, 0, 0, 0, 2, 52, 2015, ... (OEIS A099882).