TOPICS

# Generalized Petersen Graph

The generalized Petersen graph , also denoted (Biggs 1993, p. 119; Pemmaraju and Skiena 2003, p. 215), for and is a connected cubic 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-transitive iff 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).

Tutte proved that has a unique 3-edge-coloring.

is the Nauru graph and has LCF notation (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 , (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 nonhamiltonian iff 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.

I Graph, Petersen Graph

## Explore with Wolfram|Alpha

More things to try:

## 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.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 Web Resource. https://mathworld.wolfram.com/GeneralizedPetersenGraph.html