Petersen graph

From Wikipedia, the free encyclopedia

The Petersen graph is a small graph that serves as a useful example and counterexample in graph theory. The graph is named for Julius Petersen, who published it in 1898. Petersen constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.^[1] Although the graph is generally credited to Petersen, it had in fact first appeared 12 years earlier, in 1886.^[2]

Contents 1 Properties 1.1 Basic properties 1.2 Other properties 1.3 Largest and smallest 2 As counterexample 3 Generalized Petersen graphs 4 Petersen graph family 5 Notes 6 References

[edit] Properties

[edit] Basic properties

The Petersen graph ...

• is 3-connected and hence 3-edge-connected and bridgeless. See the glossary.
• has independence number 4 and is 3-partite. See the glossary.
• is cubic, is strongly regular, has domination number 3, and has a perfect matching and a 2-factor. See the glossary.
• has radius 2 and diameter 2.
• has chromatic number 3 and chromatic index 4, making it a snark. (To see that there is no 3-edge-coloring requires checking four cases.) It was the only known snark from 1898 until 1946.

[edit] Other properties

The Petersen graph ...

• is nonplanar. It has as minors both the complete graph K₅ (contract the five short edges in the first picture), and the complete bipartite graph K_3,3.
• has crossing number 2.
• can be embedded in the projective plane with six pentagonal faces.
• has a Hamiltonian path but no Hamiltonian cycle.
• is symmetric, meaning that it is edge transitive and vertex transitive.
• is one of only five known connected vertex transitive graphs with no Hamiltonian cycle. It is conjectured that there are no others.
• is hypohamiltonian, meaning that although it has no Hamiltonian cycle, deleting any vertex makes it Hamiltonian. See this embedding for a demonstration of the hypohamiltonian property.
• is one of only 14 cubic distance-regular graphs.^[3]
• is the complement of the line graph of K₅.
• is a unit distance graph, meaning it can be drawn in the plane with all the edges length 1.
• has automorphism group the symmetric group S₅.
• is the Kneser graph KG_5,2. (This means you get the Petersen graph from the following construction: Take the 2-element subsets of a 5-element set as vertices, and connect two vertices if they are disjoint as sets.)
• is the graph formed by the vertices and edges of the hemi-dodecahedron, that is, a dodecahedron with opposite points, lines and faces identified together.
• has graph spectrum −2, −2, −2, −2, 1, 1, 1, 1, 1, 3.
• has Thue number five

Every homomorphism of the Petersen graph to itself that doesn't identify adjacent vertices is an automorphism.

[edit] Largest and smallest

The Petersen graph ...

• is the smallest snark.
• is the smallest bridgeless cubic graph with no Hamiltonian cycle.
• is the smallest bridgeless cubic graph with no three-edge-coloring.
• is the largest cubic graph with diameter 2.
• is the smallest hypohamiltonian graph.
• is the smallest cubic graph of girth 5. (It is the unique (3,5)-cage. In fact, since it has only 10 vertices, it is the unique (3,5)-Moore graph.)
• is the smallest connected vertex-transitive graph that is not a Cayley graph
• has 2000 spanning trees, the most of any 10-vertex cubic graph^[4].

[edit] As counterexample

The Petersen graph frequently arises as a counterexample or exception in graph theory. For example, if G is a 2-connected, r-regular graph with at most 3r + 1 vertices, then G is Hamiltonian or G is the Petersen graph.^[5]

[edit] Generalized Petersen graphs

In 1969 Mark Watkins introduced a family of graphs generalizing the Petersen graph. The generalized Petersen graph G(n,k) is a graph with vertex set

and edge set

where subscripts are to be read modulo n and k < n / 2.

The Petersen graph itself is G(5,2).

This family of graphs possesses a number of interesting properties. For example,

1. G(n,k) is vertex-transitive if and only if n = 10,k = 2 or .
2. It is edge-transitive only in the following seven cases: (n,k) = (4,1),(5,2),(8,3),(10,2),(10,3),(12,5),(24,5).
3. It is bipartite if and only if n is even and k is odd.
4. It is a Cayley graph if and only if .

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), and the Desargues graph G(10,3).

The Petersen graph itself is the only generalized Petersen graph that is not 3-edge-colorable. [Castagna and Prins, 1972]

[edit] Petersen graph family

The Petersen graph family consists of the seven graphs that can be formed from the complete graph K₆ by zero or more applications of Δ-Y or Y-Δ transforms. A graph is intrinsically linked if and only if it contains one of these graphs as a subgraph.

[edit] Notes

1. ^ The Petersen graph by Andries E. Brouwer.
2. ^ A. B. Kempe (1886). "A memoir on the theory of mathematical form". Philosophical Transactions of the Royal Society of London 177: 1–70.
3. ^ According to Cubic symmetric graphs (The Foster Census).
4. ^ Jakobson and Rivin 1999; Valdes 1991. The cubic graphs with 6 and 8 vertices maximizing the number of spanning trees are Möbius ladders.
5. ^ Holton and Sheehan, page 32

[edit] References

• Frank Castagna and Geert Prins (1972). "Every Generalized Petersen Graph has a Tait Coloring". Pacific Journal of Mathematics 40.
• Geoffrey Exoo, Frank Harary, and Jerald Kabell (1981). "The crossing numbers of some generalized Petersen graphs". Mathematica Scandinavica 48: 184–188.
• D. A. Holton and J. Sheehan (June 1, 1993). The Petersen Graph. Cambridge University Press. ISBN 0-521-43594-3. Available on Google print.
• Jakobson, Dmitry; Rivin, Igor (1999). "On some extremal problems in graph theory". arXiv:math.CO/9907050.
• Mitch Keller, Kneser graphs on PlanetMath
• László Lovász (1993). Combinatorial Problems and Exercises, second edition. North-Holland. ISBN 0-444-81504-X.
• Julius Petersen (1898). "Sur le théorème de Tait". L'Intermédiaire des Mathématiciens 5: 225–227.
• Valdes, L. (1991). "Extremal properties of spanning trees in cubic graphs". Congr. Numer. 85: 143–160.
• Mark E. Watkins (1969). "A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs". Journal of Combinatorial Theory 6: 152–164.
• Weisstein, Eric W., Petersen Graph at MathWorld.