On the adjacency properties of generalized Paley graphs (Q2760433)

Let \(m\) and \(n\) be nonnegative integers and let \(k\) be a positive integer. A graph \(G\) is said to have property \(P(m,n,k)\) if for any \(m+n\) distinct vertices of \(G\) there are at least \(k\) other vertices, each of which is adjacent to the first \(m\) vertices but not adjacent to any of the latter \(n\) vertices. It is known that almost all graphs have property \(P(m,n,k)\). However, for the case \(m,n\geq 2\), almost no such graphs have been constructed, with the only known examples being Paley graphs, which are defined as follows. For \(q\equiv 1\pmod 4\) a prime power, the Paley graph \(G_q\) of order \(q\) is the graph whose vertices are elements of the finite field \(\mathbb{F}_q\) with two vertices adjacent if and only if their difference is a quadratic residue. By using higher-order residues on finite fields the author generates other classes of graphs which he refers to as genealized Paley graphs. He then shows that, for any \(m\), \(n\) and \(k\), all sufficiently large (order) graphs obtained by taking cubic and quadruple residues have property \(P(m,n,k)\).