On eigenfunctions and maximal cliques of generalised Paley graphs of square order

Sergey Goryainov, Leonid Shalaginov, Chi Hoi Yip

Published 2022-03-30Version 1

Let $GP(q^2,m)$ be the $m$-Paley graph defined on the finite field with order $q^2$. We study eigenfunctions and maximal cliques in generalised Paley graphs $GP(q^2,m)$, where $m \mid (q+1)$. In particular, we explicitly construct maximal cliques of size $\frac{q+1}{m}$ or $\frac{q+1}{m}+1$ in $GP(q^2,m)$, and show the weight-distribution bound on the cardinality of the support of an eigenfunction is tight for the smallest eigenvalue $-\frac{q+1}{m}$ of $GP(q^2,m)$. These new results extend the work of Baker et. al and Goryainov et al. on Paley graphs of square order. We also study the stability of the Erd\H{o}s-Ko-Rado theorem for $GP(q^2,m)$ (first proved by Sziklai).