I have proved that every Paley graph $P(p^{2})$ over $p^{2}$ vertices, where $p\geq 5$ is a prime number has a cospectral mate, i.e. for every prime number $p\geq 5$ there exists a graph $\Gamma_{p}$ such that $P(p^{2})$ and $\Gamma_{p}$ are cospectral but non-isomorphic. Is it well-known? If so, Could one please giving me the references?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
Choose a projective plane of order $p$, where $p$ is odd. Choose a line and view it as a line at infinity. Choose a partition of the points on the line into two classes $C_0$ and $C_1$ of size $(p+1)/2$. Now construct a graph on the affine points, the $p^2$ points not on the line, where two affine points are adjacenct if the line through them meets the line at infinity at a point in $C_0$. The resulting graph is a conference graph and so is cospectral with the Paley graph on $p^2$ vertices.
There is a problem: we have to decide if the graph is isomorphic to a Paley graph. For moderate values this can be decided by computer. The computational evidence is that we get large families of non-isomorphic graphs using the above construction. But there is a construction of conference graphs on $q^2$ vertices due to Peisert ("All Self-Complementary Symmetric Graphs"). Here $q$ is a power of a prime $p$, and Peisert focusses on the graphs when $p\equiv3$ mod 4, because the graphs in this case are arc-transitive and self-complementary. But his construction works when $p\cong1$ mod 4, as shown in Natalie Mullin's M.Math thesis: https://uwspace.uwaterloo.ca/bitstream/handle/10012/4264/nm_thesis.pdf?sequence=1 So we do know that if $p>3$ then a Paley graph on $p^2$ vertices is not determined by its spectrum. (There may well be earlier proofs of this.)
It is possible that the graphs you have constructed are new.
I believe that if $p\equiv1$ mod 4 and $p\ge29$, the Paley graph on $p$ vertices is not determined by its spectrum. But this is only proved when $p=29$ (by computer search); for larger $p$ I am not aware of any construction. This is a very interesting question.
answered Nov 24, 2013 at 20:36
-
$\begingroup$ I think that in the mentioned thesis it is proved that Paley graph and Dickson semifield graph are cospectral non-isomorphic graphs but the order of proper semifield, i.e. a finite semifield which is not a field, must be $p^{n}$, where $p$ is a prime number, $n$ is an integer greater than 2 and $p^{n}$ is greater than 8. Therefore i think that this result does not imply my result. Is it true? $\endgroup$ Commented Nov 24, 2013 at 21:23
-
2$\begingroup$ Yes, this result does not imply your result for small primes. But for small primes Brouwer's tables of srgs indicate that the Paley graphs are not determined by their spectrum. Also your proof may well be interesting in its own right. (I am just trying to point you to what's known.) $\endgroup$ Commented Nov 24, 2013 at 22:15
-
$\begingroup$ I have faced some problems to construct cospectral non-isomorphic graph with $P(p^{2})$ from the thesis for large prime number $p$. would you please giving me some more explanation. $\endgroup$ Commented Nov 25, 2013 at 11:45