graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, the generalized Petersen graphs are a family of

cubic graph In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs. A bicubic graph is a cubic bipa ...

s formed by connecting the vertices of a

regular polygon In Euclidean geometry, a regular polygon is a polygon that is direct equiangular (all angles are equal in measure) and equilateral (all sides have the same length). Regular polygons may be either convex, star or skew. In the limit, a sequence ...

to the corresponding vertices of a

star polygon In geometry, a star polygon is a type of non- convex polygon. Regular star polygons have been studied in depth; while star polygons in general appear not to have been formally defined, certain notable ones can arise through truncation operation ...

. They include the

Petersen graph In the mathematics, mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertex (graph theory), vertices and 15 edge (graph theory), edges. It is a small graph that serves as a useful example and counterexample for ...

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 + , a combination of the

Schläfli symbol In geometry, the Schläfli symbol is a notation of the form \ that defines regular polytopes and tessellations. The Schläfli symbol is named after the 19th-century Swiss mathematician Ludwig Schläfli, who generalized Euclidean geometry to mor ...

s for the regular ''n''-gon and

from which the graph is formed. The Petersen graph itself is ''G''(5, 2) or + . 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 In geometry, a dodecahedron (Greek , from ''dōdeka'' "twelve" + ''hédra'' "base", "seat" or "face") or duodecahedron is any polyhedron with twelve flat faces. The most familiar dodecahedron is the regular dodecahedron with regular pentag ...

''G''(10, 2), the

Desargues graph In the mathematical field of graph theory, the Desargues graph is a distance-transitive, cubic graph with 20 vertices and 30 edges. It is named after Girard Desargues, arises from several different combinatorial constructions, has a high le ...

''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: * ''G''(''n'', ''k'') is

vertex-transitive In geometry, a polytope (e.g. a polygon or polyhedron) or a tiling is isogonal or vertex-transitive if all its vertices are equivalent under the symmetries of the figure. This implies that each vertex is surrounded by the same kinds of fa ...

(meaning that it has symmetries that take any vertex to any other vertex) if and only if (''n'', ''k'') = (10, 2) or ''k''² ≡ ±1 (mod ''n''). * ''G''(''n'', ''k'') is

edge-transitive In geometry, a polytope (for example, a polygon or a polyhedron) or a Tessellation, tiling is isotoxal () or edge-transitive if its Symmetry, symmetries act Transitive group action, transitively on its Edge (geometry), edges. Informally, this mea ...

(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 Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definit ...

generalized Petersen graphs. * ''G''(''n'', ''k'') is bipartite if and only if ''n'' is even and ''k'' is odd. * ''G''(''n'', ''k'') is a

Cayley graph In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Ca ...

if and only if ''k''² ≡ 1 (mod ''n''). * ''G''(''n'', ''k'') is hypohamiltonian when ''n'' is congruent to 5 modulo 6 and ''k'' = 2, ''n'' − 2, or (''n'' ± 1)/2 (these four choices of ''k'' lead to isomorphic graphs). It is also non- Hamiltonian when ''n'' is divisible by 4, at least equal to 8, and ''k'' = ''n''/2. In all other cases it has a

Hamiltonian cycle In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...

. When ''n'' is congruent to 3 modulo 6 ''G''(''n'', 2) 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 6 and involves the

Fibonacci number In mathematics, the Fibonacci numbers, commonly denoted , form a integer sequence, sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start ...

s. * Every generalized Petersen graph is a

unit distance graph In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these gr ...

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: :

g(G(n,k)) \le \min \left \.

A table with exact girth values:

Chromatic number and chromatic index

Being

regular The term regular can mean normal or in accordance with rules. It may refer to: People * Moses Regular (born 1971), America football player Arts, entertainment, and media Music * "Regular" (Badfinger song) * Regular tunings of stringed instrum ...

, according to

Brooks' theorem In graph theory, Brooks' theorem states a relationship between the maximum degree of a graph and its chromatic number. According to the theorem, in a connected graph in which every vertex has at most Δ neighbors, the vertices can be colored with o ...

their

chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

can not be larger than their

degree Degree may refer to: As a unit of measurement * Degree (angle), a unit of angle measurement ** Degree of geographical latitude ** Degree of geographical longitude * Degree symbol (°), a notation used in science, engineering, and mathemati ...

. Generalized Petersen graphs are cubic, so their chromatic number can be either 2 or 3. More exactly: :

\chi(G(n,k))= \begin
  2 & 2 \mid n \land 2 \nmid k \\
  3 & 2 \nmid n \lor 2 \mid k \\
\end

Where

\land

denotes the logical AND, while

\lor

the logical OR. For example, the chromatic number of

G(5,2)

is 3. Petersen_graph_3-coloring.svg, A 3-coloring of the

G(5,2)

Desargues graph 2COL.svg, A 2-coloring of the

G(10,3)

Dürer graph 3COL.svg, A 3-coloring of the Dürer graph or

G(6,2)

, being a snark, has a

chromatic index In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue ...

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. PetersenBarveniHran.svg, A 4-edge-coloring of the

G(5,2)

Dürer graph 3color edge.svg, A 3-edge-coloring of the Dürer graph or

G(6,2)

3-colored dodecahedron.svg, A 3-edge-coloring of the

G(10,2)

Desargues graph 3color edge.svg, A 3-edge-coloring of the

G(10,3)

Symmetric group 4; Cayley graph 1,5,21 (Nauru Petersen); matrices.svg, A 3-edge-coloring of the Nauru graph or

G(12,5)

The Petersen graph itself is the only generalized Petersen graph that is not 3- edge-colorable..

References

{{reflist Parametric families of graphs Regular graphs