networkx.generators.expanders.paley_graph¶
-
paley_graph(p, create_using=None)[source]¶ Returns the Paley (p-1)/2-regular graph on p nodes.
The returned graph is a graph on Z/pZ with edges between x and y if and only if x-y is a nonzero square in Z/pZ.
If p = 1 mod 4, -1 is a square in Z/pZ 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 = 3 mod 4, -1 is not a square in Z/pZ and therefore either x-y or y-x is a square in Z/pZ 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 Z/pZ. 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
p (int, an odd prime number.)
create_using (NetworkX graph constructor, optional (default=nx.Graph)) – Graph type to create. If graph instance, then cleared before populated.
- Returns
G – The constructed directed graph.
- Return type
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).