The Paley graph of order 
with 
a prime power satisfying 
is a graph on 
nodes with two distinct nodes adjacent iff their difference is 
for a nonzero
element 
of 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 order of the graph automorphism group of the Paley graph of order 
, where 
is a prime number and 
is a positive
integer, is given by
 |
(Peisert 2001).
Paley graphs are implemented in the Wolfram Language as GraphData["Paley",
q] for small orders 
.
Cyclotomic graphs are cubic analogs of the Paley graphs.
The Paley graph 
is a strongly regular graph with parameters
(Godsil and
Royle 2001, p. 221). For 
a prime number, Paley graphs
are also circulant graphs 
with parameters 
given by the nonzero quadratic
residues modulo 
.
Paley graphs are self-complementary, strongly regular, conference graphs, and Hamiltonian (Godsil and Royle 2001, p. 222). Each Paley graph is isomorphic to its graph distance graph at distance 2, which is its graph complement.
Special cases include the cycle graph 
(5-Paley), 
-generalized quadrangle
(9-Paley), and 
-Paulus graph (25-Paley).
The 13-Paley graph is toroidal, as illustrated above. The first graph embedding patch appears in Jones (2020, p. 157).
The 17-Paley graph is, up to graph isomorphism, the unique largest graph 
such that neither 
nor its graph complement
contains 
as a subgraph (Evans et al. 1981). This graph
gives the lower bound 
for the Ramsey number. Together with the upper bound
of Greenwood and Gleason (1955), this yields 
.
Broere et al. (1988) showed that the clique number and chromatic number for 
with 
an even power of a prime
number are both 
.
J. B. Shearer maintains a table of the independence
numbers of Paley graphs for graphs of order
less than 7000, and Brouwer maintains a table of independence
numbers and chromatic numbers for Paley graphs
up to 
.
) with Square Differences." Indag. Math. 46,
369-372, 1984.Bondy, J. A. and Murty, U. S. R.