On the adjacency properties of generalized Paley graphs.
Watcharaphong Ananchuen · 2001
Let m and n be non-negative integers and 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. We know that almost all graphs have property P(m, n, k). However, for the case m, n 2:: 2, almost no such graphs 'have been constructed, with the only known examples being Paley graphs which are defined as follows. For q = = 1 (mod 4) a prime power, the Payley graph Gq of order q is the graph whose vertices are elements of the finite field F q; two vertices a and b are adjacent if and only if their difference is a quadratic residue. By using higher order residues on finite fields we can generate other classes of graphs which we refer to as generalized Paley graphs. For any m, nand k, we show that all sufficiently large (order) graphs obtained by taking cubic and quadruple residues have property P(m, n, k).