Paley graphs

The graphs that bear his name are constructed as follows: Given a finite field F with q elements, make a graph with vertex set F where two vertices are joined when their difference is a square in the field. This is an undirected graph when q is congruent 1 (mod 4).

For q = 4t + 1, the parameters are v = 4t + 1, k = 2t, λ = t − 1, μ = t.

Examples (q = 5 and q = 9):

For q = 13 the Paley graph is locally a hexagon, so that the graph is a quotient of the hexagonal grid:

(More generally, the graph on the elements of GF(q), where q=6t+1, where x and y are adjacent when (y−x)⁶ = 1, is locally a hexagon, unless q is a power of 7.)

Paley graphs are isomorphic to their complements: if a is a nonsquare, then the map that sends x to ax is an isomorphism from the graph to its complement.

Independence and chromatic number

In I. Broere, D. Döman, J. N. Ridley, The clique numbers and chromatic numbers of certain Paley graphs, Quaestiones Math. 11 (1988) 91-93, it is shown that when q is an even power of a prime, the clique and chromatic number are both sqrt(q). (Indeed, this is trivial: the subfield gives a clique, and its translates give a partitions into cliques. No larger cliques exist by the Hoffman bound. But the graph is self-complementary.)

A much stronger result is found in A. Blokhuis, On subsets of GF(q²) with square differences, Indag. Math. 46 (1984) 369-372. This paper shows that if a subset of GF(q) has size sqrt(q) and all differences are squares, or all differences are nonsquares, then the subset is the affine image of a subfield. In particular, this determines all cliques and all cocliques of size sqrt(q) in the Paley graph of order q.

Smaller maximal cliques are constructed in R. D. Baker, G. L. Ebert, J. Hemmeter, A. J. Woldar, Maximal cliques in the Paley graph of square order, J. Statist. Plann. Inference 56 (1996) 33-38.

A small table with independence numbers and chromatic numbers:

Dominating sets

Similarly, for Paley tournaments P(q) one has:

Reference