most recent 30 from http://mathoverflow.net 2013-05-21T21:00:33Z http://mathoverflow.net/feeds/question/83214 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/83214/spectrum-and-degree-sequence Shahrooz 2011-12-11T23:07:06Z 2011-12-11T23:34:43Z

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

http://mathoverflow.net/questions/83214/spectrum-and-degree-sequence/83217#83217 Chris Godsil 2011-12-11T23:34:43Z 2011-12-11T23:34:43Z

<p>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$.</p> <p>You can find some of the theory on line at <a href="http://www.cs.yale.edu/homes/spielman/561/lect23-09.pdf" rel="nofollow">http://www.cs.yale.edu/homes/spielman/561/lect23-09.pdf</a></p>