Module generalized_petersen 

Generalized Petersen graph constructor (ALGO-CN-010).

Counterpart of igraph_generalized_petersen() in references/igraph/src/constructors/generalized_petersen.c:58-95.

The generalized Petersen graph G(n, k) has 2n vertices in two layers:

• outer cycle v_0, v_1, …, v_{n-1} — a cycle C_n over ids 0..n.
• inner circulant u_0, u_1, …, u_{n-1} — circulant graph over ids n..2n where u_i is connected to u_{(i + k) mod n}.
• rungs — every v_i is connected to its inner counterpart u_i.

It has exactly 3n edges: n outer-cycle edges, n rung edges, and n inner-circulant edges.

G(5, 2) is the classic Petersen graph. Other famous specializations include G(8, 3) (Möbius–Kantor), G(10, 3) (Desargues), and G(12, 5) (Nauru).

Constraints (mirroring upstream):

• n >= 3.
• 0 < k < n / 2 (note: strict — 2k < n).

Returns an undirected graph in all cases — the upstream C constructor is fixed-direction (IGRAPH_UNDIRECTED).

Reference: M. E. Watkins, A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs, Journal of Combinatorial Theory 6, 152–164 (1969).

Time complexity: O(|V|) = O(n).

Functions

generalized_petersen

Build the generalized Petersen graph G(n, k).