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 regularStrongly 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 .
Alexander, J. "Designs From Paley Graphs and Peisert Graphs." 16 Oct 2015. https://arxiv.org/abs/1507.01289.Baker,
R. D.; Ebert, G. L.; Hemmeter, J.; Woldar, A. J. "Maximal Cliques
in the Paley Graph of Square Order." J. Statist. Plann. Inference56,
33-38, 1996.Blokhuis, A. "On Subsets of GF() 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."
http://www.win.tue.nl/~aeb/drg/graphs/Paley.html.Brouwer,
A. E.; Cohen, A. M.; and Neumaier, A. "Conference Matrices and Paley
Graphs." In Distance
Regular Graphs. New York: Springer-Verlag, p. 10, 1989.Brouwer,
A. E. and van Lint, J. H. "Strongly Regular Graphs and Partial Geometries."
In Enumeration
and Design: Papers from the conference on combinatorics held at the University of
Waterloo, Waterloo, Ont., June 14-July 2, 1982 (Ed. D. M. Jackson
and S. A. Vanstone). Toronto, Canada: Academic Press, pp. 85-122,
1984.Chandler, D. B.; Sin, P.; and Xiang, Q. "The Smith and
Critical Groups of Paley Graphs." J. Algebraic Combin.41.4, 1013-1022,
2015.DistanceRegular.org. "Paley Graphs." https://www.math.mun.ca/distanceregular/indexes/paleygraphs.html.Erdős,
P. and Rényi, A. "Asymmetric Graphs." Acta Math. Acad. Sci. Hungaricae14,
295-315, 1963.Evans, R. J.; Pulham, J. R.; and Sheehan, J.
"On the Number of Complete Subgraphs Contained in Certain Graphs." J.
Combin. Th. Ser. B30, 364-371, 1981.Godsil, C. and Royle,
G. Algebraic
Graph Theory. New York: Springer-Verlag, pp. 221-222, 2001.Jones,
G. A. "Paley and the Paley Graphs." In Isomorphisms,
Symmetry and Computations in Algebraic Graph Theory: Pilsen, Czech Republic, October
3-7, 2016 (Ed. G. A. Jones, I. Ponomarenko, and J. Širáň).
Cham, Switzerland: Springer Nature, pp. 155-183, 2020.Muzychuk,
M. E. "Automorphism Groups of Paley Graphs and Cyclotomic Schemes."
In Isomorphisms,
Symmetry and Computations in Algebraic Graph Theory: Pilsen, Czech Republic, October
3-7, 2016 (Ed. G. A. Jones, I. Ponomarenko, and J. Širáň).
Cham, Switzerland: Springer Nature, pp. 185-194, 2020.Peisert,
W. "All Self-Complementary Symmetric Graphs." J. Algebra240,
209-229, 2001.Sachs, H. "Über selbstkomplement'are graphen."
Pub. Math. Debrecen9, 270-288, 1962.Seidel, J. J.
"Graphs and Two-Graphs." In Proc. 5th Southeast Conf. Comb., Graph Th.,
Comp. (Ed. F. Hoffman et al.). Winnipeg, Canada: Utilitas Mathematica
Pub., pp. 125-143, 1974.Shearer, J. B. "Independence
Numbers of Paley Graphs." http://www.research.ibm.com/people/s/shearer/indpal.html.Sloane,
N. J. A. Sequence A085759 in "The
On-Line Encyclopedia of Integer Sequences."
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).
or 
(Brouwer et al. 1989, p. 10), where "QR"
stands for quadratic residue.
is given by
.
is strongly regularStrongly 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 
).
(5-Paley), 
-generalized quadrangle
(9-Paley), and 
-Paulus graph (25-Paley).
such that neither 
nor its graph complement
contains 
as a subgraph (Evans et al. 1981). It follows
from this graph that Ramsey number 
.
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."