Haemers Conjecture

In general, it is difficult to determine if a graph is determined by spectrum. van Dam and Haemers (van Dam and Haemers 2002, Haemers 2016) noted that it is conceivable that almost all graphs have this property, i.e., that the fraction of graphs on n vertices with a cospectral mate tends to zero as n tends to infinity, an assertion sometimes known as Haemer's conjecture (Brouwer and Spence 2009, Wang and Wang 2024).

See also

Cospectral Graphs, Determined by Spectrum, Graph Spectrum

Explore with Wolfram|Alpha


Brouwer, A. E. and Spence, E. "Cospectral Graphs on 12 Vertices." Elect. J. Combin., Vol. 16, No. 1, 2009., 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, 139-162, 2003.Wang, W. and Wang, W. "Haemers' Conjecture: An Algorithmic Perspective." Experimental Math., 10 Apr 2024.

Cite this as:

Weisstein, Eric W. "Haemers Conjecture." From MathWorld--A Wolfram Web Resource.

Subject classifications