# Generalized Petersen graph

Jump to navigation Jump to search

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

{u0, u1, ..., un−1, v0, v1, ..., vn−1}

and edge set

{ui ui+1, ui vi, vi vi+k: i = 0,...,n − 1}

where subscripts are to be read modulo n and k < n/2. Some authors use a similar notation GPG(n,k) with the same meaning.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.

Any generalized Petersen graph can also be constructed from a voltage graph with two vertices, two self-loops, and one other edge.

The Petersen graph itself is G(5,2) or {5}+{5/2}.

## 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 One of the three Hamiltonian cycles in G(9,2). The other two Hamiltonian cycles in the same graph are symmetric under 40° rotations of the drawing.

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

1. G(n,k) is vertex-transitive (meaning that it has symmetries that take any vertex to any other vertex) if and only if n = 10 and k =2 or if k2 ≡ ±1 (mod n).
2. It is edge-transitive (having symmetries that take any edge to any other edge) only in the following seven cases: (n,k) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5), (24,5). These seven graphs are therefore the only symmetric generalized Petersen graphs.
3. It is bipartite if and only if n is even and k is odd.
4. It is a Cayley graph if and only if k2 ≡ 1 (mod n).
5. It is hypohamiltonian when n is congruent to 5 modulo 6 and k is 2, n−2, (n+1)/2, or (n−1)/2 (all four of these choices of k lead to isomorphic graphs). It is also non-Hamiltonian when n is divisible by four, at least equal to 8, and k is n/2. In all other cases it has a Hamiltonian cycle. When n is congruent to 3 modulo 6 and k is 2, G(n,k) has exactly three Hamiltonian cycles. For G(n,2), the number of Hamiltonian cycles can be computed by a formula that depends on the congruence class of n modulo six and involves the Fibonacci numbers.

Every generalized Petersen graph is a unit distance graph.

### Isomorphisms

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

### Girth

The girth of a generalized Petersen graph, g(G(n,k)) is at least 3 and at most 8, in particular G(PG(n,k)) ≤ $\min\{8,k+3,n/\gcd\{n,k\}\}$ .

A table with exact girth values:

Condition Girth
$n=3k$ 3
$n=4k$ 4
$k=1$ $n=5k$ 5
$n=5k/2$ $k=2$ $n=6k$ 6
$k=3$ $n=2k+2$ $n=7k$ 7
$n=7k/2$ $n=7k/3$ $k=4$ $n=2k+3$ $n=3k\pm 2$ otherwise 8

### Chromatic number and chromatic index

Being regular, according to Brooks' theorem their chromatic number can not be larger than their degree. Generalized Petersen graphs are cubic, so their chromatic number can be either 2 or 3. More exactly:

$\chi (\operatorname {G} (n,k))={\begin{cases}2&2\mid n\land 2\nmid k\\3&2\nmid n\lor 2\mid k\end{cases}}$ Where $\land$ denotes the logical AND, while $\lor$ the logical OR. For example, the chromatic number of $\operatorname {G} (5,2)$ is 3.

Petersen graph, being a snark, has a chromatic index of 4. All other generalized Petersen graph has chromatic index 3.

The generalized Petersen graph 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.