Generalized Paley graphs equienergetic with their complements

Abstract

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