TOPICS
Search

Cospectral Graphs

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
CospectralGraphs

Cospectral graphs, also called isospectral graphs, are graphs whose adjacency matrices have the same eigenvalues, counted with multiplicity, and hence the same graph spectrum. The smallest pair of nonisomorphic cospectral simple graphs consists of the graph union C_4 union K_1 and star graph S_5, illustrated at left above, both of which have graph spectrum (-2)0^32 (Skiena 1990, p. 85). Regular cospectral graphs are of particular interest. The smallest nonisomorphic regular cospectral simple graphs have 10 vertices. Two pairs of quartic graphs of this order are illustrated above center and right (Cvetković et al. 1998, p. 398; van Dam and Haemers 2003, p. 245).

CospectralGraphsTriple

The smallest triple of pairwise nonisomorphic, cospectral connected simple graphs has seven vertices. Up to graph isomorphism, this triple is unique. Each graph has 11 edges, and their common characteristic polynomial is

det(xI-A)=x^7-11x^5-10x^4+16x^3+16x^2,

where A is the adjacency matrix (Brouwer; Brouwer and Spence 2009, p. 2).

The first example of cospectral graphs was found by Collatz and Sinogowitz (1957) (Biggs 1993, p. 12). Many examples are given in Cvetković et al. (1998, pp. 156-161) and Rücker et al. (2002).

The following table summarizes some prominent named cospectral graphs.

ncospectral graphs
126-antiprism graph, quartic vertex-transitive graph Qt19
16Hoffman graph, tesseract graph Q_4
16(4,4)-rook graph, Shrikhande graph
2525-Paulus graphs
2626-Paulus graphs
28Chang graphs, 8-triangular graph
70Harries graph, Harries-Wong graph

Determining which graphs are uniquely determined by their spectra is in general a very hard problem. The Haemers conjecture asserts that the proportion of simple graphs on n vertices, counted up to graph isomorphism, that are determined by spectrum tends to 1 as n->infty (van Dam and Haemers 2003, pp. 241-242; Haemers 2016).

Brouwer and Spence (2009) determined the numbers of unlabeled graphs with a nonisomorphic cospectral mate among simple graphs on n vertices for n<=12. For n=1, 2, ..., these numbers are 0, 0, 0, 0, 2, 10, 110, 1722, 51039, 2560606, 215331676, 31067572481, ... (OEIS A006608). The numbers of complete cospectral classes of exactly two unlabeled graphs are 0, 0, 0, 0, 1, 5, 52, 771, 21025, ... (OEIS A099881). Similarly, the numbers of complete cospectral classes of exactly three unlabeled graphs are 0, 0, 0, 0, 0, 0, 2, 52, 2015, ... (OEIS A099882).

See also

Determined by Spectrum, Graph Eigenvalue, Graph Spectral Distance, Graph Spectrum, Hoffman Graph, Isospectral Manifolds, Shrikhande Graph

Explore with Wolfram|Alpha

References

Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, p. 12, 1993.Brouwer, A. E. "Numbers of Characteristic Polynomials and Cospectral Graphs for A." https://aeb.win.tue.nl/graphs/cospectral/cospectralA.html.Brouwer, A. E. and Spence, E. "Cospectral Graphs on 12 Vertices." Elec. J. Combin. 16, No. 1, N20, 2009. https://doi.org/10.37236/258.Collatz, L. and Sinogowitz, U. "Spektren endlicher Grafen." Abh. Math. Sem. Univ. Hamburg 21, 63-77, 1957.Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.Godsil, C. D. and McKay, B. D. "Constructing Cospectral Graphs." Aeq. Math. 25, 257-268, 1982.Haemers, W. H. "Are Almost All Graphs Determined by Their Spectrum?" Not. S. Afr. Math. Soc. 47, 42-45, 2016.Haemers, W. H. and Spence, E. "Graphs Cospectral with Distance-Regular Graphs." Linear Multilin. Alg. 39, 91-107, 1995.Rücker, C.; Rücker, G.; and Meringer, M. "Exploring the Limits of Graph Invariant- and Spectrum-Based Discrimination of (Sub)structures." J. Chem. Inf. Comp. Sci. 42, 640-650, 2002.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 85, 1990.Sloane, N. J. A. Sequences A006608, A099881, and A099882in "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, 2002. https://doi.org/10.1023/A:1013847004932.van Dam, E. R. and Haemers, W. H. "Which Graphs Are Determined by Their Spectrum?" Lin. Algebra Appl. 373, 241-272, 2003. https://doi.org/10.1016/S0024-3795(03)00483-X.

Referenced on Wolfram|Alpha

Cospectral Graphs

Cite this as:

Weisstein, Eric W. "Cospectral Graphs." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CospectralGraphs.html

Subject classifications