chordal_cycle_graph

chordal_cycle_graph(p, create_using=None)

Returns the chordal cycle graph on p nodes.

The returned graph is a cycle graph on p nodes with chords joining each vertex x to its inverse modulo p. This graph is a (mildly explicit) 3-regular expander [1] when viewed as a simple graph. The default return type is a MultiGraph, which has 6-regular nodes due to the symmetric nature of the edge additions. Use nx.Graph(nx.chordal_cycle_graph(p)) to obtain the 3-regular simple graph.

p must be a prime number.

Parameters:

pa prime number

The number of vertices in the graph. This also indicates where the chordal edges in the cycle will be created.

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

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

Returns:

Ggraph

The constructed undirected multigraph.

Raises:

NetworkXError

If create_using indicates directed or not a multigraph.

References

[1]

Theorem 4.4.2 in A. Lubotzky. “Discrete groups, expanding graphs and invariant measures”, volume 125 of Progress in Mathematics. Birkhäuser Verlag, Basel, 1994.