Generalized Petersen graph

Examples

Among the generalized Petersen graphs are the ${\displaystyle n}$-prism ${\displaystyle G(n,1)}$, the Dürer graph ${\displaystyle G(6,2)}$, the Möbius-Kantor graph ${\displaystyle G(8,3)}$, the dodecahedron ${\displaystyle G(10,2)}$, the Desargues graph ${\displaystyle G(10,3)}$ and the Nauru graph ${\displaystyle G(12,5)}$.

Four generalized Petersen graphs – the 3-prism, the 5-prism, the Dürer graph, and ${\displaystyle 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:

• ${\displaystyle G(n,k)}$ is vertex-transitive (meaning that it has symmetries that take any vertex to any other vertex) if and only if ${\displaystyle (n,k)=(10,2)}$ or ${\displaystyle k^2\equiv \pm 1(\mathrm{m}\mathrm{o}\mathrm{d}n)}$.
• ${\displaystyle G(n,k)}$ is edge-transitive (having symmetries that take any edge to any other edge) only in the following seven cases: ${\displaystyle (n,k)}$ is (4, 1), (5, 2), (8, 3), (10, 2), (10, 3), (12, 5), or (24, 5). These seven graphs are therefore the only symmetric generalized Petersen graphs.
• ${\displaystyle G(n,k)}$ is bipartite if and only if ${\displaystyle n}$ is even and ${\displaystyle k}$ is odd.
• ${\displaystyle G(n,k)}$ is a Cayley graph if and only if ${\displaystyle k^2\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}n)}$.
• ${\displaystyle G(n,k)}$ is hypohamiltonian when ${\displaystyle n}$ is congruent to 5 modulo 6 and ${\displaystyle k}$ is 2, ${\displaystyle n-2}$, or ${\displaystyle (n\pm 1)/2}$ (these four choices of k lead to isomorphic graphs). It is also non-Hamiltonian when ${\displaystyle n}$ is divisible by 4, at least equal to 8, and ${\displaystyle k=n/2}$. In all other cases it has a Hamiltonian cycle. When ${\displaystyle n}$ is congruent to 3 modulo 6, ${\displaystyle G(n,2)}$ has exactly three Hamiltonian cycles. For ${\displaystyle G(n,2)}$, the number of Hamiltonian cycles can be computed by a formula that depends on the congruence class of ${\displaystyle n}$ modulo 6 and involves the Fibonacci numbers. Linear recurrence relations for the number of Hamiltonian cycles have also been found for ${\displaystyle G(n,3)}$ and ${\displaystyle G(n,4)}$.
• Every generalized Petersen graph is a unit distance graph.

Isomorphisms

${\displaystyle G(n,k)}$ is isomorphic to ${\displaystyle G(n,\ell )}$ if and only if ${\displaystyle k\equiv \pm \ell (\mathrm{m}\mathrm{o}\mathrm{d}n)}$ or ${\displaystyle k\ell \equiv \pm 1(\mathrm{m}\mathrm{o}\mathrm{d}n)}$.

Girth

The girth of ${\displaystyle G(n,k)}$ is at least 3 and at most 8, in particular:

${\displaystyle g(G(n,k))\le min\left\{8,k+3,\frac{n}{gcd(n,k)}\right\}.}$

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:

${\displaystyle \chi (G(n,k))=\{\begin{array}{ll}2& 2\mid n\wedge 2\nmid k\\ 3& 2\nmid n\vee 2\mid k\end{array}}$

Where ${\displaystyle \wedge }$ denotes the logical AND, while ${\displaystyle \vee }$ the logical OR. Here, ${\displaystyle \mid }$ denotes divisibility, and ${\displaystyle \nmid }$ denotes its negation. For example, the chromatic number of ${\displaystyle G(5,2)}$ 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 ${\displaystyle G(9,2)}$ 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.