Let $p$ be a prime number greater than or equal to 11. Are there any cospectral non-isomorphic graphs with circulant graphs on $p$ vertices. Which circulant graphs over prime number of vertices greater than or equal to 11 are determined by the spectrum?
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
No, and you don't need $p\ge 11$ either.
B Elspas, J Turner Graphs with circulant adjacency matrices, J. Combinatorial Theory, 9 (1970), pp. 297–307.
This paper shows that no two non-isomorphic circulant graphs on a prime number of vertices have the same spectrum. It doesn't say anything about circulant graphs cospectral with non-circulant graphs.
answered Sep 16, 2014 at 8:43
$\begingroup$
$\endgroup$
6
We know that all groups with prime order is CI-group. So, if two circulant graph with $p$ vertices be cospectral, then they are isomorphic. So, as Dear Brendan said, the answer is no.
But about your comment, the answer is yes. Just look at strongly regular graphs of order $29$. In this order we have Paley graph that is circulant, but also we have exactly $40$ other graphs that are cospectral with this graph and some of them are not circulant. You can see the page $856$ of book: $Handbook\; of\; combinatorial\; design$.
For $p=11$ the asnwer is yes. All circulant graphs with $11$ vertices are DS. Also, All circulant graphs with $13$ vertices are DS. But, as I said for $p=29$ there are at least $40$ non-isomorphic graphs cospectral with Paley graph. So, the answer to this question is not known in general and I think it is very hard by some evidences.
-
$\begingroup$ Thank you but is there any general answer. $\endgroup$ Commented Sep 16, 2014 at 10:43
-
$\begingroup$ In general, the answer is no, even for special type of graphs. $\endgroup$– ShahroozCommented Sep 16, 2014 at 11:01
-
$\begingroup$ "All circulant graphs on $p$ vertices, where $p$ is greater than or equal to 11 are not determined by the spectrum" $\endgroup$ Commented Sep 16, 2014 at 11:10
-
$\begingroup$ This statement is true or false? $\endgroup$ Commented Sep 16, 2014 at 11:11
-
1$\begingroup$ You have to say whether you want the spectrum to determine the graphs within the class of circulant graphs or within the class of all graphs. This distinction is key to understanding the difference between Shahrooz's answer and mine. $\endgroup$ Commented Sep 17, 2014 at 4:14