Generalized Petersen Graph

The generalized Petersen graph , also denoted (Biggs 1993, p. 119; Pemmaraju and Skiena 2003, p. 215), for and is a connected cubic graph consisting of an inner star polygon (circulant graph ) and an outer regular polygon (cycle graph ) with corresponding vertices in the inner and outer polygons connected with edges. These graphs were introduced by Coxeter (1950) and named by Watkins (1969). They should not be confused with the seven Petersen family graphs.

Here, is the floor function.

For even, the -generalized Petersen graph is sometimes defined (Alspach 1983) even though, unlike usual generalized Petersen graphs, such graphs are not cubic.

For a cubic generalized Petersen graph, , where is the edge count and is the vertex count. More specifically, has nodes and edges when . The degenerate case has edges.

Generalized Petersen graphs are implemented in the Wolfram Language as PetersenGraph[n, k] and their properties are available using GraphData["GeneralizedPetersen", n, k].

Generalized Petersen graphs may be further generalized to I graphs.

If , then is isomorphic to by interchanging the inner and outer vertices and relabeling their indices. For example, , , , , and so on. The numbers of nonisomorphic generalized Petersen graphs on , 8, ... nodes are 1, 1, 2, 2, 2, 3, 3, 4, 3, 5, 4, 5, 6, 6, 5, 7, ... (OEIS A077105).

is vertex-transitive iff or , and symmetric only for the cases , (5, 2), (8, 3), (10, 2), (10, 3), (12, 5), and (24, 5) (Frucht et al. 1971; Biggs 1993, p. 119).

No generalized Petersen graph is semisymmetric. Label its outer vertices and inner vertices , with indices taken modulo . The map , is a graph automorphism, so the adjacent vertices and lie in the same group orbit. If the graph were edge-transitive, the orbit obstruction for semisymmetric graphs would make it vertex-transitive. The degenerate case is also excluded because its outer vertices have degree three and its inner vertices have degree two, so it is not a regular graph.

Tutte proved that has a unique 3-edge coloring.

is the Nauru graph and has LCF notation (Frucht 1976).

Known positive exact graph crossing numbers and selected candidates are summarized below. Square brackets denote candidates derived from computed upper bounds, not proved exact values.

Wang and Zhang (2023) proved that the projective plane crossing number of is for . For , they established the bounds .

All generalized Petersen graphs are unit-distance graphs (Žitnik et al. 2010). However, the only generalized Petersen indices (some of which correspond to the same graph) which are unit-distance by twisting correspond to , (6, 2), (7, 2), (7, 3), (8, 2), (8, 3), (9, 2), (9, 3), (9, 4), (10, 2), (10, 3), (11, 2), (12, 2) (Žitnik et al. 2010).

A cubic generalized Petersen graph is nonhamiltonian iff it is isomorphic to with (Alspach 1983; Holton and Sheehan 1993, p. 316). Furthermore, the number of Hamiltonian cycles in for is given by

(1)

(Schwenk 1989; Holton and Sheehan 1993, p. 316).

The following table gives some special cases of the generalized Petersen graph.

graph	generalized Petersen graph
cubic symmetric graph
cubical graph
Desargues graph
dodecahedral graph
Dürer graph
Möbius-Kantor graph
Nauru graph
Petersen graph
prism graph

Krishnan et al. (2026) determined the remaining zero forcing number values for two subfamilies: for every and for every . The smaller values of for , 8, ..., 12 are 6, 6, 6, 8, 7, 7, and those of for , 10, ..., 17 are 6, 6, 7, 6, 8, 8, 9, 8, 9. Krishnan et al. (2026) report AI assistance with mathematical exploration, programming, and formalization.