TOPICS
Search

Cospectral Graphs


IsospectralGraphs

Cospectral graphs, also called isospectral graphs, are graphs that share the same graph spectrum. The smallest pair of isospectral graphs is the graph union C_4 union K_1 and star graph S_5, illustrated above, both of which have graph spectrum (-2)0^32 (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 C_4 union K_1 and star graph S_5, illustrated above, both of which have graph spectrum (-2)0^32 (Skiena 1990, p. 85).

The following table summarizes some prominent named cospectral graphs.

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).

The total number of n-node simple graphs that are isospectral to at least one other graph on n nodes for n=1, 2, ... are 0, 0, 0, 0, 1, 6, 110, 1722, 51039, ... (OEIS A099883). 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).


See also

Determined by Spectrum, Graph Eigenvalue, 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.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. 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 A099881, A099882, A099883 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, 2003.

Referenced on Wolfram|Alpha

Cospectral Graphs

Cite this as:

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

Subject classifications