Generalized Petersen graph

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, is a graph with vertex set
and edge set
where subscripts are to be read modulo and where. Some authors use the notation. Coxeter's notation for the same graph would be, a combination of the Schläfli symbols for the regular -gon and star polygon from which the graph is formed. The Petersen graph itself is or. Some authors also allow, producing a graph that is not a regular graph.
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 -prism, the Dürer graph, the Möbius-Kantor graph, the dodecahedron, the Desargues graph and the Nauru graph.
Four generalized Petersen graphs – the 3-prism, the 5-prism, the Dürer graph, and – are among the seven graphs that are cubic, 3-vertex-connected, and well-covered.

Properties

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

is vertex-transitive if and only if or.
is edge-transitive only in the following seven cases: is,,,,,, These seven graphs are therefore the only symmetric generalized Petersen graphs.
is bipartite if and only if is even and is odd.
is a Cayley graph if and only if.
is hypohamiltonian when is congruent to 5 modulo 6 and is 2,, or . It is also non-Hamiltonian when is divisible by 4, at least equal to 8, and. In all other cases it has a Hamiltonian cycle. When is congruent to 3 modulo 6, has exactly three Hamiltonian cycles. For, the number of Hamiltonian cycles can be computed by a formula that depends on the congruence class of modulo 6 and involves the Fibonacci numbers. Linear recurrence relations for the number of Hamiltonian cycles have also been found for and.
Every generalized Petersen graph is a unit distance graph.

Isomorphisms

is isomorphic to if and only if or.

Girth

The girth of is at least 3 and at most 8, in particular:
A table with exact girth values:

Condition	Girth
	3
	4
	4
	5
	5
	5
	6
	6
	6
	7
	7
	7
	7
	7
	7
otherwise	8

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 denotes the logical AND, while the logical OR. Here, denotes divisibility, and denotes its negation. For example, the chromatic number of is 3.
The Petersen graph, being a snark, has a chromatic index of 4: its edges require four colors. All other generalized Petersen graphs have chromatic index 3. These are the only possibilities, by Vizing's theorem.
The generalized Petersen graph is one of the few graphs known to have only one 3-edge-coloring.
The Petersen graph itself is the only generalized Petersen graph that is not 3-edge-colorable.