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?
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
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.
answered Mar 18, 2016 at 8:15
-
$\begingroup$ You don't claim there is no SRG counterexample on 35 vertices, right? $\endgroup$– joroCommented Mar 18, 2016 at 8:20
-
$\begingroup$ no, I don't, I just don't know how to see an example quickly. While for the example I provide it is trivial. $\endgroup$ Commented Mar 18, 2016 at 9:59
$\begingroup$
$\endgroup$
0
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.
answered Mar 18, 2016 at 10:50
$\begingroup$
$\endgroup$
6
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.
-
1$\begingroup$ 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...) $\endgroup$ Commented Mar 18, 2016 at 10:20
-
$\begingroup$ Thank you! I'll verify that whether these graphs are circulants soon. $\endgroup$ Commented Mar 18, 2016 at 10:35
-
1$\begingroup$ 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. $\endgroup$ Commented Mar 18, 2016 at 10:50
-
$\begingroup$ Using Sage, I find that the first graph in maths.gla.ac.uk/~es/SRGs/29-14-6-7 is not a circulant. $\endgroup$ Commented Mar 18, 2016 at 13:18
-
$\begingroup$ @XueyiHuang I didn't claim this. I wrote "Paley graphs of prime order are SRG circulants" $\endgroup$– joroCommented Mar 18, 2016 at 13:42