TOPICS
Search

Haemers Conjecture

The Haemers conjecture asserts that almost all graphs are determined by spectrum. van Dam and Haemers (2003) suggested that the fraction of graphs on n vertices with a cospectral mate tends to zero as n tends to infinity (Brouwer and Spence 2009, Haemers 2016, Wang and Wang 2024).

A weaker version uses the generalized graph spectrum, consisting of the spectra of a graph and its graph complement. Xiang (2026) reported that a random graph sampled from G(n,1/2) is determined by this pair with probability tending to 1 as n->infty. The original conjecture using only the graph spectrum remains open. Xiang (2026) describes the paper as a collaboration with Claude Opus 5.5.

See also

Cospectral Graphs, Determined by Spectrum, Generalized Graph Spectrum, Graph Spectrum

Explore with Wolfram|Alpha

References

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.Haemers, W. H. "Are Almost All Graphs Determined by Their Spectrum?" Not. S. Afr. Math. Soc. 47, 42-45, 2016.van Dam, E. R. and Haemers, W. H. "Which Graphs Are Determined by Their Spectrum?" Lin. Algebra Appl. 373, 241-272, 2003.Wang, W. and Wang, W. "Haemers' Conjecture: An Algorithmic Perspective." Experimental Math., 10 Apr 2024.Xiang, Z. "Almost All Graphs Are Determined by Their Generalized Spectrum." 8 Oct 2026. https://arxiv.org/abs/2610.11047.

Referenced on Wolfram|Alpha

Haemers Conjecture

Cite this as:

Weisstein, Eric W. "Haemers Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/HaemersConjecture.html

Subject classifications