Dürer graph.svg G(6, 2) .]] In graph theory, the generalized Petersen graphs are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. They include the Petersen graph and generalize one of the ways of constructing the Petersen graph. The generalized Petersen graph family was introduced in 1950 by H. S. M. Coxeter and was given its name in 1969 by Mark Watkins.

Definition and notation

In Watkins' notation, G(n, k) is a graph with vertex set and edge set where subscripts are to be read modulo n and k < n/2. Some authors use the notation GPG(n, k). Coxeter's notation for the same graph would be {n} + {n/k}, a combination of the Schläfli symbols for the regular n-gon and star polygon from which the graph is formed. The Petersen graph itself is G(5, 2) or {5} + {5/2}. Any generalized Petersen graph can also be constructed from a voltage graph with two vertices, two self-loops, and one other edge.

Examples

Among the generalized Petersen graphs are the n-prism G(n, 1), the Dürer graph G(6, 2), the Möbius-Kantor graph G(8, 3), the dodecahedron G(10, 2), the Desargues graph G(10, 3) and the Nauru graph G(12, 5). Four generalized Petersen graphs – the 3-prism, the 5-prism, the Dürer graph, and G(7, 2) – are among the seven graphs that are cubic, 3-vertex-connected, and well-covered (meaning that all of their maximal independent sets have equal size).

Properties

This family of graphs possesses a number of interesting properties. For example:

Isomorphisms

G(n, k) is isomorphic to G(n, l) if and only if k=l or kl ≡ ±1 (mod n).

Girth

The girth of G(n, k) is at least 3 and at most 8, in particular: A table with exact girth values:

Chromatic number and chromatic index

Generalized Petersen graphs are regular graphs of degree three, so according to Brooks' theorem their chromatic number can only be two or three. More exactly: Where \land denotes the logical AND, while \lor the logical OR. Here, \mid denotes divisibility, and \nmid denotes its negation. For example, the chromatic number of G(5,2) is 3. The Petersen graph itself is the only generalized Petersen graph that is not 3-edge-colorable.

Perfect Colorings

All admissible matrices of all perfect 2-colorings of the graphs G(n, 2) and G(n, 3) are enumerated.