The Paley graph of order
with a prime power
is a graph on
nodes with two nodes adjacent if their difference is a square in the finite
field GF().
This graph is undirected when . Simple Paley graphs therefore exist for orders
5, 9, 13, 17, 25, 29, 37, 41, 49, 53, 61, 73, 81, 89, 97, 101, 109, 113, 121, 125,
137, 149, 157, 169, ... (OEIS A085759).
Paley graphs are commonly denoted or (Brouwer et al. 1989, p. 10), where "QR"
stands for quadratic residue.
The Paley graph
is strongly regular with parameters (Godsil and Royle 2001, p. 221).
For a prime, Paley graphs are also circulant
graphs
with parameters
given by the squares (mod ).
The 17-Paley graph is the unique largest graph such that neither nor its graph complement
contains
as a subgraph (Evans et al. 1981). It follows
from this graph that Ramsey number .
Broere et al. (1988) showed that the clique number and chromatic number for with an even power of a prime are both . J. B. Shearer maintains a table of the independence
numbers of Paley graphs for graphs of size less than 7000, and Brouwer maintains
a table of independence and chromatic numbers for Paley graphs up to .