Paley graphs over $p^{2}$ vertices 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? 
 A: 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.
