# Classes of graphs for which isospectrum implies isomorphism ?

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 ?

-
Is the answer to this question expected to be substantially the same for the adjacency matrix and the Laplacian? – Qiaochu Yuan Dec 13 '10 at 22:53
That's something I was wondering about as well. the references mostly talk about the adjacency matrix. – Suresh Venkat Dec 13 '10 at 23:10
I think the answer to this question certainly does depend on whether you use the adjacency matrix or the Laplacian. But it doesn't really matter for the related question: are almost all graphs determined by their spectra? This is because basically for regular graphs all the different notions of spectra coincide. – Tony Huynh Dec 13 '10 at 23:17

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.

-
I think I see why (at least for regular of degree 2), but is it obvious and I'm missing something ? the class of graphs you're describing are disjoint collections of cycles and paths, and so I presume the argument is that each component then sets off a distinct spectral signature ? – Suresh Venkat Dec 13 '10 at 9:03
Correct (if I have not made an error) See win.tue.nl/~aeb/2WF02/easyspectra.pdf for the details. Most trees are not determined by their spectra but some people think that most graphs are. – Aaron Meyerowitz Dec 13 '10 at 9:39
I'm not sure maximum degree two or complete count as "interesting" classes of graphs, do they :-) – Gordon Royle Dec 13 '10 at 11:54
that's a nice reference. and yes, I meant the first version, but both are interesting. – Suresh Venkat Dec 13 '10 at 23:09

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.

-

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.

-
Well, the class of graphs of vertex degree at most two is closed under passage to covering spaces. Also you needn't worry about covering spaces if you are looking at classes of trees. Still, your point is well-taken. – Pete L. Clark Dec 13 '10 at 22:17