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(\mathrm{mod}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(\mathrm{mod}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).