## spectrum and degree sequence

We have the spectrum and the degree sequence of one graph. Can we uniquely determine the graph with these given information?

-
 Do you mean Laplacian spectrum or adjacency spectrum? In any case, most examples of cospectral pairs also have the same degree sequence. – Gjergji Zaimi Dec 11 2011 at 23:27 I do not think it is true that in most examples of cospectral pairs the graphs have the same degree sequence. It's not true for small numbers of vertices, $(n\le 9 say?). I suspect that many do have the same degree sequence, but I've never seen a discussion of the matter. For larger$n$your guess might be as good as mine. – Chris Godsil Dec 11 2011 at 23:39 ## 1 Answer No. One simple class of examples are Latin square graphs. If$L$is an$n\times n$Latin square with entries from${1,\ldots,n}$, the vertices of Latin square graph are the$n^2$triples; two triples are adjacent if the agree on one of their three coordinates. This is a regular graph of valency$3(n-1)$. In fact these graphs are strongly regular, and their eigenvalues are$3(n-1)$,$n$and$-3$with respective multiplicities 1,$n-3$and$n^2-3n+2$. Two Latin squares give non-isomorphic graphs in they are in different main classes (see the wikipedia article) and there are many main classes for large$n$. When$n=4$there are two, and over a quarter of a million when$n=8\$.

You can find some of the theory on line at http://www.cs.yale.edu/homes/spielman/561/lect23-09.pdf

-
 I think it is true if we know our graph has at least n(n-1)/K(G) edges, where V(G)=n and 2=