# 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?

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.

• You don't claim there is no SRG counterexample on 35 vertices, right? – joro Mar 18 '16 at 8:20
• no, I don't, I just don't know how to see an example quickly. While for the example I provide it is trivial. – Dima Pasechnik Mar 18 '16 at 9:59

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.

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.

• regarding circulants, the first obvious case to try is the graphs with Paley graph parameters (29,14,6,7) on 29 vertices. If anyone cares, these graphs are given here maths.gla.ac.uk/~es/SRGs/29-14-6-7 (converting them into Sage-readable format would be great...) – Dima Pasechnik Mar 18 '16 at 10:20
• Thank you! I'll verify that whether these graphs are circulants soon. – Xueyi Huang Mar 18 '16 at 10:35
• One of them is surely a circulant (the Paley graph). I bet some (most?) of them do not have a transitive automorphism group, and this cannot be Cayley graphs. – Dima Pasechnik Mar 18 '16 at 10:50
• Using Sage, I find that the first graph in maths.gla.ac.uk/~es/SRGs/29-14-6-7 is not a circulant. – Xueyi Huang Mar 18 '16 at 13:18
• @XueyiHuang I didn't claim this. I wrote "Paley graphs of prime order are SRG circulants" – joro Mar 18 '16 at 13:42