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[1] and was given its name in 1969 by Mark Watkins.[2]
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 {n} + {n/k}, a combination of the
Schläfli symbols for the
regular n-gon and
star polygon from which the graph is formed. The Petersen graph itself is G(5, 2) or {5} + {5/2}.
Any generalized Petersen graph can also be constructed from a
voltage graph with two vertices, two self-loops, and one other edge.[3]
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:
G(n, k) is
vertex-transitive (meaning that it has symmetries that take any vertex to any other vertex) if and only if (n, k) = (10, 2) or k2 ≡ ±1 (mod n).
G(n, k) 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).[5] These seven graphs are therefore the only
symmetric 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 if and only if k2 ≡ 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.[6] When n is congruent to 3 modulo 6 G(n, 2) has exactly three Hamiltonian cycles.[7] 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 numbers.[8]
G(n, k) is isomorphic to G(n, l) if and only if k=l or kl ≡ ±1 (mod n).[10]
Girth
The
girth of G(n, k) is at least 3 and at most 8, in particular:[11]
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:
Where denotes the logical
AND, while the logical
OR. Here, denotes divisibility, and denotes its negation. For example, the chromatic number of is 3.
^Gross, Jonathan L.; Tucker, Thomas W. (1987), Topological Graph Theory, New York: Wiley. Example 2.1.2, p.58.
^Campbell, S. R.;
Ellingham, M. N.;
Royle, Gordon F. (1993), "A characterisation of well-covered cubic graphs", Journal of Combinatorial Mathematics and Combinatorial Computing, 13: 193–212,
MR1220613.
^Frucht, R.; Graver, J. E.; Watkins, M. E. (1971), "The groups of the generalized Petersen graphs", Proceedings of the Cambridge Philosophical Society, 70 (2): 211–218,
doi:
10.1017/S0305004100049811.
^Karami, Hamed (2022), "Perfect 2-colorings of the generalized Petersen graph GP(n,3)", Electronic Journal of Graph Theory and Applications, 10: 239–245,
arXiv:2009.07120,
doi:10.5614/ejgta.2022.10.1.16.