Paley graph

This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (December 2023) (Learn how and when to remove this message)

Paley graph
The Paley graph of order 13
Named after	Raymond Paley
Vertices	q ≡ 1 mod 4, q prime power
Edges	q(q − 1)/4
Diameter	2
Properties	Strongly regular Conference graph Self-complementary
Notation	QR(q)
Table of graphs and parameters

In mathematics, Paley graphs are undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ by a quadratic residue. The Paley graphs form an infinite family of conference graphs, which yield an infinite family of symmetric conference matrices. Paley graphs allow graph-theoretic tools to be applied to the number theory of quadratic residues, and have interesting properties that make them useful in graph theory more generally.

Paley graphs are named after Raymond Paley. They are closely related to the Paley construction for constructing Hadamard matrices from quadratic residues (Paley 1933). They were introduced as graphs independently by Sachs (1962) and Erdős & Rényi (1963). Sachs was interested in them for their self-complementarity properties, while Erdős and Rényi studied their symmetries.

Paley digraphs are directed analogs of Paley graphs that yield antisymmetric conference matrices. They were introduced by Graham & Spencer (1971) (independently of Sachs, Erdős, and Rényi) as a way of constructing tournaments with a property previously known to be held only by random tournaments: in a Paley digraph, every small subset of vertices is dominated by some other vertex.