Are almost all graphs determined by their spectrum?

Importance: High ✭✭✭
Subject: Graph Theory
Recomm. for undergrads: no
Posted by: mdevos
on: March 26th, 2013

\begin{problem} Are almost all graphs uniquely determined by the spectrum of their adjacency matrix? \end{problem}

We say that two non-isomorphic graphs are \emph{cospectral} if their adjacency matrices have the same spectrum (counted with multiplicity). A graph is \emph{spectrally determined} if no other graphs are cospectral to it. It is unclear to me (M. DeVos) how to attribute this problem, but it was considered already in the 1950's and resonates with the famous problem "Can you hear the shape of a drum?" ([vDH]).

A priori, it might seem plausible for all graphs to be spectrally determined.. but this is false. The smallest counterexample is the cospectral pair given by $K_{1,4}$ and the graph obtained from $C_4$ by adding an isolated vertex. Some rich families of cospectral graphs are provided by strongly regular graphs, since any two strongly regular graphs with the same parameters will be cospectral.

For the special case of trees, Schwenk proved almost all trees are not spectrally determined. This was sharpened by Godsil and Mckay who showed that almost every tree $T$ has a cospectral graph $T'$ so that in addition the complements of $T$ and $T'$ are cospectral. Furthermore, an operation called \emph{Godsil-Mckay Switching} defined by these authors gives a powerful tool to produce general graphs which are cospectral.

On the flip side, we seem to have a lack of good tools to prove that a given graph is spectrally determined.

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{}


[vDH] E. R. van Dam and W. H. Haemers, Which graphs are determined by their spectrum?, Linear Algebra and its Applications 373 (2003) 241–272.

% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

* indicates original appearance(s) of problem.