Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 ?

share|improve this question
    
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
add comment

3 Answers

up vote 5 down vote accepted

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.

share|improve this answer
    
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
2  
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
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.