Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Generalized Petersen graph
Summary
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 and was given its name in 1969 by Mark Watkins.
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.
Among the generalized Petersen graphs are the n-prism G(n, 1), the Dürer graph G(6, 2), the Möbius-Kantor graph G(8, 3), the dodecahedron G(10, 2), the Desargues graph G(10, 3) and the Nauru graph G(12, 5).
Four generalized Petersen graphs – the 3-prism, the 5-prism, the Dürer graph, and G(7, 2) – are among the seven graphs that are cubic, 3-vertex-connected, and well-covered (meaning that all of their maximal independent sets have equal size).
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). 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).
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.