On eigenfunctions and maximal cliques of Paley graphs of square order

Sergey Goryainov, Vladislav V. Kabanov, Leonid Shalaginov, Alexandr Valyuzhenich

Published 2018-01-01Version 1

In this paper we find new maximal cliques of size $\frac{q+1}{2}$ or $\frac{q+3}{2}$, accordingly as $q\equiv 1(4)$ or $q\equiv 3(4)$, in Paley graphs of order $q^2$, where $q$ is an odd prime power. After that we use new cliques to define a family of eigenfunctions corresponding to both non-principal eigenvalues and having the cardinality of support $q+1$, which is the minimum by the weight-distribution bound.