Generalized Petersen Graph

👁 DOWNLOAD Mathematica Notebook
Download Wolfram Notebook

The generalized Petersen graph 👁 GP(n,k)
, also denoted 👁 P(n,k)
(Biggs 1993, p. 119; Pemmaraju and Skiena 2003, p. 215), for 👁 n>=3
and 👁 1<=k<=|_(n-1)/2_|
is a connected cubic graph consisting of an inner star polygon 👁 {n,k}
(circulant graph 👁 Ci_n(k)
) and an outer regular polygon 👁 {n}
(cycle graph 👁 C_n
) 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.

For 👁 n
even, the 👁 (n,n/2)
-generalized Petersen graph is sometimes defined (Alspach 1983) even though, unlike usual generalized Petersen graphs, such graphs are not cubic.

Since the generalized Petersen graph is cubic, 👁 m/n=3/2
, where 👁 m
is the edge count and 👁 n
is the vertex count. More specifically, 👁 GP(n,k)
has 👁 2n
nodes and 👁 3n
edges.

Generalized Petersen graphs are implemented in the Wolfram Language as [k, n] and their properties are available using [👁 {
, 👁 {
k, n👁 }
👁 }
].

Generalized Petersen graphs may be further generalized to I graphs.

For 👁 n
odd, 👁 GP(n,k)
is isomorphic to 👁 GP(n,(n-2k+3)/2)
. So, for example, 👁 GP(7,2)=GP(7,3)
, 👁 GP(9,2)=GP(9,4)
, 👁 GP(11,2)=GP(11,5)
, 👁 GP(11,3)=GP(11,4)
, and so on. The numbers of nonisomorphic generalized Petersen graphs on 👁 n=6
, 8, ... nodes are 1, 1, 2, 2, 2, 3, 3, 4, 3, 5, 4, 5, 6, 6, 5, 7, ... (OEIS A077105).

👁 GP(n,k)
is vertex-transitive iff 👁 k^2=+/-1 (mod n)
or 👁 (n,k)=(10,2)
, and symmetric only for the cases 👁 (n,k)=(4,1)
, (5, 2), (8, 3), (10, 2), (10, 3), (12, 5), and (24, 5) (Frucht et al. 1971; Biggs 1993, p. 119).

Tutte proved that 👁 GP(9,4)
has a unique 3-edge-coloring.

👁 GP(12,5)
is the Nauru graph 👁 F_(024)A
and has LCF notation 👁 [5,-9,7,-7,9,-5]^4
(Frucht 1976).

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 👁 (n,k)=(5,2)
, (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 👁 GP(n,k)
is nonhamiltonian iff 👁 k=2
and 👁 n=5 (mod 6)
(Alspach 1983; Holton and Sheehan 1993, p. 316). Furthermore, the number of Hamiltonian cycles in 👁 GP(n,2)
for 👁 n>=3
is given by

(Schwenk 1989; Holton and Sheehan 1993, p. 316).

The following table gives some special cases of the generalized Petersen graph.

See also

I Graph, Petersen Graph

Explore with Wolfram|Alpha

References

Alspach, B. R. "The Classification of Hamiltonian Generalized Petersen Graphs." J. Combin. Th. Ser. B 34, 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.Goedgebeur, J.; Neyt, A.; and Zamfirescu, C. T. "Structural and Computational Results on Platypus Graphs." Appl. Math. Comput., 386:125491, 10 pages, 2020.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č Saražin, M. "A Note on the Generalized Petersen Graphs That Are Also Cayley Graphs." J. Combin. Th. B 69, 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. B 47, 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.

Referenced on Wolfram|Alpha

Generalized Petersen Graph

Cite this as:

Weisstein, Eric W. "Generalized Petersen Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GeneralizedPetersenGraph.html

Subject classifications