Generalized Paley graphs equienergetic with their complements

Abstract

We consider generalized Paley graphs $\Gamma (k,q)$, generalized Paley sum graphs ${\Gamma }^{+}(k,q)$, and their corresponding complements $\bar{\Gamma }(k,q)$ and ${\bar{\Gamma }}^{+}(k,q)$, for $k=3,4$. Denote by $\Gamma ={\Gamma }^{\ast }(k,q)$ either $\Gamma (k,q)$ or ${\Gamma }^{+}(k,q)$. We compute the spectra of $\Gamma (3,q)$ and $\Gamma (4,q)$ and from them we obtain the spectra of ${\Gamma }^{+}(3,q)$ and ${\Gamma }^{+}(4,q)$ also. Then we show that, in the non-semiprimitive case, the spectrum of $\Gamma (3,p^{3\ell })$ and $\Gamma (4,p^{4\ell })$ with $p$ prime can be recursively obtained, under certain arithmetic conditions, from the spectrum of the graphs $\Gamma (3,p)$ and $\Gamma (4,p)$ for any $\ell \in \mathbb{N}$, respectively. Using the spectra of these graphs we give necessary and sufficient conditions on the spectrum of ${\Gamma }^{\ast }(k,q)$ such that ${\Gamma }^{\ast }(k,q)$ and ${\bar{\Gamma }}^{\ast }(k,q)$ are equienergetic for $k=3,4$. In a previous work we have classified all bipartite regular graphs ${\Gamma }_{bip}$ and all strongly regular graphs ${\Gamma }_{srg}$ which are complementary equienergetic, i.e.\@ $\{{\Gamma }_{bip},{\bar{\Gamma }}_{bip}\}$ and $\{{\Gamma }_{srg},{\bar{\Gamma }}_{srg}\}$ are equienergetic pairs of graphs. Here we construct infinite pairs of equienergetic non-isospectral regular graphs $\{\Gamma ,\bar{\Gamma }\}$ which are neither bipartite nor strongly regular.

22 pages