arvau

Wikipedia / 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

, a combination of the Schläfli symbols for the regular n-gon and star polygon, 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

, the Dürer graph, the Möbius-Kantor graph, the dodecahedron, the Desargues graph and the Nauru graph.

– 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

.

Girth

The girth is at least 3 and at most 8, in particular:

A table with exact girth values:

Condition

Girth

3

4

5

6

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:

denotes the logical AND the logical OR 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.

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.

References