Graphs cospectral with Cayley graphs Let $G$ be a Cayley graph, and $H$ a graph cospectral with $G$. Must $H$ be a Cayley graph? Does a counterexample exist? If $G$ is a circulant graph, does a counterexample exist?
 A: To rectify joro's answer; he is certainly correct about the general direction, although it is not clear from his answer whether any of these 35-vertex SRGs is Cayley.
However, on 25 vertices there are a number of SRGs of degree 12, one of them is a certainly a Cayley graph (the Paley graph), and several SRGs with the same parameters (25,12,5,6) (hence the same spectrum) have intransitive automorphism group.
A: There are 32548 strongly regular graphs with parameters (36,15,6,6). (See the tables by Brower.) A few of these are Cayley graphs.  (For example, set S:={(1,0),(2,0),(3,0),(4,0),(5,0),(0,1),(0,2),(0,3),(0,4),(0,5),(1,1),(2,2),(3,3),(4,4),(5,5)} in $G=Z_6 \oplus Z_6$.)  The number of Cayley graphs is single digits, so there are about 32,540+ graphs with the same eigenvalues but not Cayley graphs!
Moreover, at least in the theory of strongly regular graphs, one can sometimes move from one graph to another, without changing eigenvalues, by switching on a certain vertex set. This process of switching will surely change the automorphism group and usually destroy the "Cayley" property.
A: I believe the answer is negative and a counterexample might be strongly regular graph.
On 35 vertices there are 3854 SRGs, all cospectral.
SRG need not be Cayley.

Since Paley graphs of prime order are SRG circulants, this approach may settle the second question too.
