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 order of the graph automorphism group of the Paley graph of order 
is given by
 |
(Peisert 2011).
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 strongly regular graph with parameters
(Godsil and
Royle 2001, p. 221). For 
a prime, Paley graphs are also circulant
graphs 
with parameters 
given by the squares (mod 
).
Paley graphs are self-complementary, strongly regular, conference graphs, and Hamiltonian. All Paley graph are conference graphs (Godsil and Royle 2001, p. 222). Paley graphs are their own graph distance-2 graphs.
Special cases include the cycle graph 
(5-Paley), 
-generalized quadrangle
(9-Paley), and 
-Paulus graph (25-Paley).
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 
.
) with Square Differences." Indag. Math. 46,
369-372, 1984.Broere, I.; Döman, D.; and Ridley, J. N. "The
Clique Numbers and Chromatic Numbers of Certain Paley Graphs." Quaestiones
Math. 11, 91-93, 1988.Brouwer, A. E. "Paley Graphs."