Classes of graphs for which isospectrum implies isomorphism?

Question

The spectrum of a graph is the (multi)set of eigenvalues of its adjacency matrix (or Laplacian, depending on what you're interested in). In general, two non-isomorphic graphs might have the same spectrum.

Prompted in part by this discussion on reverse engineering a graph from its spectrum, I was wondering:

Are there interesting classes of graphs for which isospectrality implies isomorphism ?

Answer 1

Maximum degree 2 would be such a class (which includes regular of degree $2$ as a subclass). Transitive graphs (by which I mean that the relation of being connected by an edge is transitive) are another example (there is a less obscure description of that class of graphs but I wanted it to sound mysterious for a few moments).

I assume that you are asking for a class $\mathcal{C}$ of graphs such that $G,H \in \mathcal{C}$ and $G,H$ cospectral implies isomorphism. If you mean classes of graphs $\mathcal{C}$ such that $G \in \mathcal{C}$ and $G,H$ cospectral implies isomorphism, then http://mathworld.wolfram.com/DeterminedbySpectrum.html might be worth a look.

Answer 2

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.

Answer 3

If you consider a class of graphs which is closed under taking covering spaces, then this is likely not to work, since one may then apply Sunada's method to construct isospectral pairs.