# paley_graph#

paley_graph(p, create_using=None)[source]#

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).