paley_graph

paley_graph(p, create_using=None)

Returns the Paley \(\frac{(p-1)}{2}\) -regular graph on \(p\) nodes.

The returned graph is a graph on \(\mathbb{Z}/p\mathbb{Z}\) with edges between \(x\) and \(y\) if and only if \(x-y\) is a nonzero square in \(\mathbb{Z}/p\mathbb{Z}\).

If \(p \equiv 1 \pmod 4\), \(-1\) is a square in \(\mathbb{Z}/p\mathbb{Z}\) and therefore \(x-y\) is a square if and only if \(y-x\) is also a square, i.e the edges in the Paley graph are symmetric.

If \(p \equiv 3 \pmod 4\), \(-1\) is not a square in \(\mathbb{Z}/p\mathbb{Z}\) and therefore either \(x-y\) or \(y-x\) is a square in \(\mathbb{Z}/p\mathbb{Z}\) but not both.

Note that a more general definition of Paley graphs extends this construction to graphs over \(q=p^n\) vertices, by using the finite field \(F_q\) instead of \(\mathbb{Z}/p\mathbb{Z}\). This construction requires to compute squares in general finite fields and is not what is implemented here (i.e paley_graph(25) does not return the true Paley graph associated with \(5^2\)).

Parameters:

pint, an odd prime number.

create_usingNetworkX graph constructor, optional (default=nx.Graph)

Graph type to create. If graph instance, then cleared before populated.

Returns:

Ggraph

The constructed directed graph.

Raises:

NetworkXError

If the graph is a multigraph.

References

Chapter 13 in B. Bollobas, Random Graphs. Second edition. Cambridge Studies in Advanced Mathematics, 73. Cambridge University Press, Cambridge (2001).