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, ... (Sloane's A085759).
Paley graphs are commonly denoted  or  (Brouwer et
al. 1989, p. 10), where "QR" stands for quadratic residue.
Cyclotomic graphs are cubic
analogs of the Paley graphs.
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  ).
Paley graphs are self-complementary, strongly regular, conference
graphs, and Hamiltonian. All
Paley graph are conference graphs,
thought the converse is not true (Godsil and Royle 2001, p. 222).
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 complement
graph contains  as a subgraph
(Evans et al. 1981). It follows from this graph that Ramsey number  .
Baker, R. D.; Ebert, G. L.; Hemmeter, J.; Woldar, A. J. "Maximal Cliques in the Paley Graph of Square Order." J. Statist. Plann. Inference 56,
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.
Evans, R. J.; Pulham, J. R.; and Sheehan, J. "On the Number of Complete Subgraphs Contained in Certain Graphs." J. Combin. Th. Ser. B 30,
364-371, 1981.
Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, pp. 221-222,
2001.
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.
Sloane, N. J. A. Sequence A085759 in "The On-Line Encyclopedia of Integer Sequences."
|
Contact the MathWorld Team
