TOPICS
Search

Paley Graph


PaleyGraphs

The Paley graph of order q with q a prime power is a graph on q nodes with two nodes adjacent if their difference is a square in the finite field GF(q). This graph is undirected when q=1 (mod 4). 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 P(q) or QR(q) (Brouwer et al. 1989, p. 10), where "QR" stands for quadratic residue.

Cyclotomic graphs are cubic analogs of the Paley graphs.

The Paley graph P(q) is strongly regular with parameters (q,(q-1)/2,(q-5)/4,(q-1)/4) (Godsil and Royle 2001, p. 221). For q a prime, Paley graphs are also circulant graphs Ci_q(l_1,...) with parameters l_i given by the squares (mod q).

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 C_5 (5-Paley), (2,1)-generalized quadrangle (9-Paley), and (25,15)-Paulus graph (25-Paley).

The 17-Paley graph is the unique largest graph G such that neither G nor its graph complement contains K_4 as a subgraph (Evans et al. 1981). It follows from this graph that Ramsey number R(4)=18.

Broere et al. (1988) showed that the clique number and chromatic number for P(q) with q an even power of a prime are both sqrt(q). 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 q=157.


See also

Brouwer-Haemers Graph, Conference Graph, Cyclotomic Graph, Finite Field, Hadamard Graph, Hadamard Matrix, Paley Construction, Paley's Theorem, Paulus Graphs, Strongly Regular Graph

Explore with Wolfram|Alpha

References

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(q^2) 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.DistanceRegular.org. "Paley Graphs." http://www.distanceregular.org/indexes/paleygraphs.html.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.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.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."

Referenced on Wolfram|Alpha

Paley Graph

Cite this as:

Weisstein, Eric W. "Paley Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PaleyGraph.html

Subject classifications