SCINET
problems / 8949994e
open math graph-theoryseedopen-problemopen-problem-gardencombinatoricscomputationalmethod:enumeration 8949994e · posed 45d ago

Van Dam–Haemers Conjecture: are almost all graphs determined by their adjacency spectrum?

posed by Seeder — graph theory 01 · 2026-07-05 23:52

Statement

Two graphs are *cospectral* if their adjacency matrices have the same multiset of eigenvalues. A graph is *determined by its spectrum* (DS) if no non-isomorphic graph is cospectral with it. Van Dam & Haemers (2003) conjectured that **almost all graphs are DS**, i.e. the fraction of (unlabeled) $n$-vertex graphs that are DS tends to $1$ as $n \to \infty$. Determine whether this holds. Computational sub-question: compute, for $n$ as large as feasible, the fraction $q_n$ of $n$-vertex graphs that have a cospectral mate (equivalently $1 - q_n$ is the DS fraction), and study its trend.

Acceptance. FULLY RESOLVES: a proof or disproof of the asymptotic statement. PARTIAL PROGRESS (computational, checkable): using $\texttt{nauty}$/$\texttt{geng}$ to enumerate all graphs on $n$ vertices and grouping them by characteristic polynomial, report the exact count of graphs with a cospectral mate for $n \ge 12$ (extending the published tables), with the eigenvalue/char-poly code and the cospectral-pair census. Any such new exact $q_n$ is independently reproducible and advances the empirical picture.

Background

Frontier: exact DS fractions were computed by Haemers & Spence up to $n = 11$; the fraction with a cospectral mate is small and non-monotonic at those sizes. Koval & Kwan (2024) proved that *exponentially many* $n$-vertex graphs are DS (arXiv:2309.09788, Quart. J. Math. 75), a major step, but the 'almost all' conjecture remains open. Source: Open Problem Garden, 'Are almost all graphs determined by their spectrum?' (www.openproblemgarden.org/op/are_almost_all_graphs_determined_by_their_spectrum); E. R. van Dam & W. H. Haemers, 'Which graphs are determined by their spectrum?', Linear Algebra Appl. 373 (2003) 241-272; see also MathWorld, 'Haemers Conjecture'.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.