MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 added 643 characters in body

It is conjectured that almost all graphs are determined by their spectrum. It is funny that this conjecture fails spectacularly for many classes of graphs that one can think of. For example, almost all trees are not determined by their spectrum. Indeed, for almost all trees one can actually find another tree with the same spectrum.

I think the best answer to your question can be found in this paper by Wang and Xu. For each $n$ they define a class of graphs $\mathcal{H}_n$ and prove that almost all graphs in $\mathcal{H}_n$ are determined by their generalized spectrum. The generalized spectrum is the spectrum of a graph together with the spectrum of its complement. The definition of $\mathcal{H}_n$ is quite complicated, but the upshot is that they believe that $\mathcal{H}_n$ has positive density in $\mathcal{G}_n$ (the set of graphs on $n$ vertices). Apparently, numerical evidence suggests that $\mathcal{H}_n$ do have positive density. If true, this would give a class of graphs of positive density which are determined by their generalized spectra. Since many graph properties are true asymptotically with either density 0 or density 1, this would give strong evidence that almost all graphs are in fact determined by their generalized spectrum.

If you want an explicit example, here is a (slightly) non-trivial one. Evidently, the spectrum of a graph determines its number of vertices and edges. One can also show that the spectrum also determines the number of triangles. From these three observations, we have that the graphs $K_{n,n}$ are all determined by their spectra. To see this, note that $K_{n,n}$ is the unique triangle-free graph with $2n$ vertices and $n^2$ edges (by Turan's theorem). Finally, I think that if a graph is determined by its spectrum, then its complement is also determined by its spectrum. So, $K_n \sqcup K_n$ is also determined by its spectrum.

1

It is conjectured that almost all graphs are determined by their spectrum. It is funny that this conjecture fails spectacularly for many classes of graphs that one can think of. For example, almost all trees are not determined by their spectrum. Indeed, for almost all trees one can actually find another tree with the same spectrum.

I think the best answer to your question can be found in this paper by Wang and Xu. For each $n$ they define a class of graphs $\mathcal{H}_n$ and prove that almost all graphs in $\mathcal{H}_n$ are determined by their generalized spectrum. The generalized spectrum is the spectrum of a graph together with the spectrum of its complement. The definition of $\mathcal{H}_n$ is quite complicated, but the upshot is that they believe that $\mathcal{H}_n$ has positive density in $\mathcal{G}_n$ (the set of graphs on $n$ vertices). Apparently, numerical evidence suggests that $\mathcal{H}_n$ do have positive density. If true, this would give a class of graphs of positive density which are determined by their generalized spectra. Since many graph properties are true asymptotically with either density 0 or density 1, this would give strong evidence that almost all graphs are in fact determined by their generalized spectrum.