TOPICS
Search

Generalized Petersen Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
GeneralizedPetersenGraphs

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.

GeneralizedPetersenGraphsDegenerate

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 PetersenGraph[k, n] and their properties are available using GraphData[{"GeneralizedPetersen", {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

{2F_(n/2+2)-2F_(n/2-2)-2 for n=0,2 (mod 6); n for n=1 (mod 6); 3 for n=3 (mod 6); n+2F_(n/2+2)-2F_(n/2-2)-2 for n=4 (mod 6); 0 for n=5 (mod 6)
(1)

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

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

graphgeneralized Petersen graph
cubic symmetric graph F_(048)AGP(24,5)
cubical graphGP(4,1)
Desargues graphGP(10,3)
dodecahedral graphGP(10,2)
Dürer graphGP(6,2)
Möbius-Kantor graphGP(8,3)
Nauru graphGP(12,5)
Petersen graphGP(5,2)
prism graphGP(n,1)

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