Generalized Petersen graph

You can make shapes with dots and lines.

First, you draw a ring of dots. Then, you draw a star shape inside. You join the dots with lines. This makes a special family of shapes.

One famous shape is called the Petersen graph. A man named Coxeter found these shapes in 1950. A man named Watkins named them in 1969. Some of these shapes look like a box. These shapes can also have many colors. They are fun to study!

You can make shapes using dots and lines. In math, we call these shapes graphs.

One special group is the generalized Petersen graphs. You make them in a set way. First, you draw a ring of dots. These dots form a shape called a polygon. Then, you draw a star shape inside that ring. You connect the dots from the ring to the star dots.

A man named H. S. M. Coxeter found these in 1950. Later, Mark Watkins gave them their name in 1969.

These shapes have many cool traits. Some look like a box. We call those prisms. Other shapes have names like the Dürer graph or the Nauru graph. Some graphs have a special path called a Hamiltonian cycle. This is a path that visits every dot once. Some graphs have many of these paths. Others have none at all. You can also use colors on these graphs. Most of them only need three colors for their lines. But the famous Petersen graph is different. It needs four colors for its lines!

This makes it very special to study.

In math, you can build shapes using dots and lines. These shapes are called graphs. One special family is the generalized Petersen graphs.

You make them by following a set pattern. First, you draw a ring of dots called a regular polygon. Next, you draw a star shape inside that ring. You connect each dot from the outer ring to a dot in the inner star. This creates a group of shapes that share many traits.

These graphs have many different names and forms. Some look like long boxes called prisms. You might find the Dürer graph or the Nauru graph in this group. Other famous examples include the Möbius-Kantor graph and the Desargues graph. The dodecahedron is also part of this family.

Some of these shapes are very balanced. For instance, the 3-prism and the 5-prism are special. They are cubic and 3-vertex-connected. They are also well-covered, which means their maximal independent sets are all the same size.

People have studied these shapes for a long time. H. S. M. Coxeter first introduced this family in 1950. Later, a man named Mark Watkins gave them their name in 1969.

Mathematicians use different ways to write them down. Watkins used a notation with letters like G(n, k). Coxeter used a different way with Schläfli symbols. The original Petersen graph is a member of this group. It is written as G(5, 2).

These shapes have many interesting rules and patterns. Some have a special path called a Hamiltonian cycle. This is a path that visits every single dot exactly once.

Some graphs have many of these paths. For example, G(9, 2) has exactly three of them. Others have no such paths at all. You can also look at the girth of a graph. The girth is the size of the smallest loop. In these graphs, the girth is between 3 and 8.

Coloring is another way to study these graphs. You can try to color the lines so no two lines of the same color touch. Most of these graphs only need three colors for their lines. This is based on a rule called Vizing's theorem. However, the Petersen graph is a rare exception. It is a snark, which means it needs four colors for its lines.

This makes it a very important shape to study in math.

In graph theory, mathematicians study structures made of vertices and edges. One important family of these structures is the generalized Petersen graphs. These are cubic graphs, which means every vertex has exactly three edges connected to it.

They are built using a very specific geometric method. You start with a set of vertices forming a regular polygon. Then, you create a second set of vertices forming a star polygon. Finally, you connect each vertex of the outer polygon to a corresponding vertex in the inner star. This process creates a complex, symmetrical network of connections.

To describe these graphs, mathematicians use specific notation. Mark Watkins introduced a common notation written as G(n, k). In this system, n represents the number of vertices in each polygon. The variable k determines how the inner star polygon is connected. For example, the original Petersen graph is represented as G(5, 2). Some researchers also use Coxeter's notation. This method uses Schläfli symbols to describe the polygons used in the construction.

Another way to build them is through a voltage graph. This method uses two vertices, two self-loops, and one additional edge.

This family contains many famous and distinct graphs. The 3-prism and the 5-prism are simple examples within the group. More complex members include the Dürer graph and the Möbius-Kantor graph. You can also find the dodecahedron, the Desargues graph, and the Nauru graph here.

Some of these graphs share very rare properties. The 3-prism, 5-prism, Dürer graph, and G(10, 2) are all cubic and 3-vertex-connected. They are also well-covered. This means that every maximal independent set in these graphs has the same size.

History shows how these concepts were developed over time. H. S. M. Coxeter first introduced this family of graphs in 1950. It took nearly two decades for the family to receive its current name. Mark Watkins gave them the name "generalized Petersen graphs" in 1969. These researchers helped define the mathematical rules that govern how these shapes behave. Their work allowed others to categorize the many different types of symmetry found in these networks.

Symmetry is a major focus when studying these graphs. A graph is vertex-transitive if its symmetries can move any vertex to any other vertex. This only happens in a generalized Petersen graph if n or k meets specific conditions. Edge-transitivity is even rarer. A graph is edge-transitive if its symmetries can move any edge to any other edge. There are only seven symmetric generalized Petersen graphs. These include G(3, 1), G(4, 1), G(5, 2), G(8, 3), G(10, 2), G(10, 3), and G(24, 5).

Researchers also look for Hamiltonian cycles within these structures. A Hamiltonian cycle is a path that visits every vertex exactly once. Some graphs, like G(9, 2), have exactly three such cycles.

Other graphs are non-Hamiltonian, meaning no such path exists. This occurs when n is divisible by 4, is at least 8, and k is 2. Additionally, some graphs are hypohamiltonian. This happens when n is congruent to 5 modulo 6 and k is 2, 3, 4, or 5. The number of cycles in certain graphs can even be calculated using Fibonacci numbers.

Coloring is another way to analyze the complexity of these graphs. Brooks' theorem states that the chromatic number of these cubic graphs is either two or three. The chromatic number is the fewest colors needed to color vertices so no neighbors match. For example, G(3, 1) has a chromatic number of 3. Mathematicians also study the chromatic index, which involves coloring the edges. Vizing's theorem limits these possibilities to two or three. Most generalized Petersen graphs have a chromatic index of 3. However, the Petersen graph is a unique exception. It is a snark, which means its edges require four colors.

This makes it one of the few graphs known to have only one 3-edge-coloring.