The generalized Petersen graph , also denoted (Biggs 1993, p. 119; Pemmaraju and Skiena 2003,
p. 215), for and is a connectedcubic graph consisting of an inner star
polygon
(circulant graph ) and an outer regular
polygon
(cycle graph ) with corresponding vertices in the inner and outer polygons
connected with edges. These graphs were introduced by Coxeter (1950) and named by
Watkins (1969). They should not be confused with the seven Petersen
family graphs.
Since the generalized Petersen graph is cubic, , where is the edge count and is the vertex count. More
specifically, has nodes and edges.
Generalized Petersen graphs are implemented in the Wolfram Language as PetersenGraph[k,
n] and their properties are available using GraphData["GeneralizedPetersen",
k,
n].
Generalized Petersen graphs may be further generalized to I
graphs.
For
odd,
is isomorphic to . So, for example, , , , , and so on. The numbers of nonisomorphic generalized
Petersen graphs on , 8, ... nodes are 1, 1, 2, 2, 2, 3, 3, 4, 3, 5, 4, 5, 6,
6, 5, 7, ... (OEIS A077105).
is vertex-transitiveiff
or ,
and symmetric only for the cases , (5, 2), (8, 3), (10, 2), (10, 3), (12, 5), and
(24, 5) (Frucht et al. 1971; Biggs 1993, p. 119).
All generalized Petersen graphs are unit-distance graphs (itnik et al. 2010). However, the only generalized Petersen
indices (some of which correspond to the same graph) which are unit-distance by twisting
correspond to , (6, 2), (7, 2), (7, 3), (8, 2), (8, 3), (9, 2),
(9, 3), (9, 4), (10, 2), (10, 3), (11, 2), (12, 2) (itnik et al. 2010).
The generalized Petersen graph is nonhamiltonianiff and (Alspach 1983; Holton and Sheehan 1993, p. 316).
Furthermore, the number of Hamiltonian cycles in for is given by
(1)
(Schwenk 1989; Holton and Sheehan 1993, p. 316).
The following table gives some special cases of the generalized Petersen graph.
Alspach, B. R. "The Classification of Hamiltonian Generalized Petersen Graphs." J. Combin. Th. Ser. B34, 293-312,
1983.Biggs, N. L. Algebraic
Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, 1993.Bondy,
J. A. "Variations on the hamiltonian Theme." Canad. Math. Bull.15,
57-62, 1972.Coxeter, H. S. M. "Self-Dual Configurations
and Regular Graphs." Bull. Amer. Math. Soc.56, 413-455, 1950.Fiorini,
S. "On the Crossing Number of Generalized Petersen Graphs." Combinatorics
'84. Amsterdam, Netherlands: North Holland Press.Frucht, R. "A
Canonical Representation of Trivalent Hamiltonian Graphs." J. Graph Th.1,
45-60, 1976.Frucht, R.; Graver, J. E.; and Watkins, M. E.
"The Groups of the Generalized Petersen Graphs." Proc. Cambridge Philos.
Soc.70, 211-218, 1971.Holton, D. A. and Sheehan, J.
"Generalized Petersen and Permutation Graphs." §9.13 in The
Petersen Graph. Cambridge, England: Cambridge University Press, pp. 45
and 315-317, 1993.Lovrečič Sarain, M. "A Note on
the Generalized Petersen Graphs That Are Also Cayley Graphs." J. Combin.
Th. B69, 226-229, 1997.Pemmaraju, S. and Skiena, S. Computational
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge,
England: Cambridge University Press, 2003.Read, R. C. and Wilson,
R. J. An
Atlas of Graphs. Oxford, England: Oxford University Press, p. 275, 1998.Schrag,
G. and Cammack, L. "On the 2-Extendability of the Generalized Petersen Graphs."
Disc. Math.78, 169-177, 1989.Schwenk, A. "Enumeration
of Hamiltonian Cycles in Certain Generalized Petersen Graphs." J. Combin.
Th. Ser. B47, 53-59, 1989.Sloane, N. J. A. Sequence
A077105 in "The On-Line Encyclopedia
of Integer Sequences."Watkins, M. E. "A Theorem on Tait
Colorings with an Application to the Generalized Petersen Graphs." J. Combin.
Th.6, 152-164, 1969.itnik, A.; Horvat, B.; and Pisanski,
T. "All Generalized Petersen Graphs are Unit-Distances Graphs." J. Korean
Math. Soc.49, 475-491, 2012.