Petersen graph

Infobox graph
name = Petersen graph


image_caption = The Petersen graph is most commonly drawn as a pentagon with a pentagram inside, with five spokes.
namesake = Julius Petersen
vertices = 10
edges = 15
radius = 2
diameter = 2
girth = 5
chromatic_number = 3
chromatic_index = 4
properties = Cubic Strongly regular SnarkIn graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named for Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring. [citation|url=http://www.win.tue.nl/~aeb/drg/graphs/Petersen.html|title=The Petersen graph|first=Andries E.|last=Brouwer.] Although the graph is generally credited to Petersen, it had in fact first appeared 12 years earlier, in 1886. [citation|first=A. B.|last=Kempe|title=A memoir on the theory of mathematical form|journal=Philosophical Transactions of the Royal Society of London|volume=177|pages=1–70|year=1886|doi=10.1098/rstl.1886.0002.]

Constructions

The Petersen graph is the complement of the line graph of $K\_5$. It is also the Kneser graph $KG\_\{5,2\}$; this means that you can form the Petersen graph by constructing a vertex for each 2-element subset of a 5-element set, and connecting two vertices by an edge if the corresponding 2-element subsets are disjoint from each other.

Geometrically, the Petersen graph 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.

Embeddings

The Petersen graph is nonplanar. Any nonplanar graph has as minors either the complete graph $K\_5$, or the complete bipartite graph $K\_\{3,3\}$, but the Petersen graph has both as minors. The $K\_5$ minor can be formed by contracting the edges of a perfect matching, for instance the five short edges in the first picture. The $K\_\{3,3\}$ minor can be formed by deleting one vertex (for instance the central vertex of the 3-symmetric drawing) and contracting an edge incident to each neighbor of the deleted vertex.

The most common and symmetric plane drawing of the Petersen graph, as a pentagram within a pentagon, has five crossings. However, this is not the best drawing for minimizing crossings; there exists another drawing (shown in the figure) with only two crossings. Thus, the Petersen graph has crossing number 2. On a torus the Petersen graph can be drawn without edge crossings; it therefore has orientable genus 1.

The Petersen graph can also be drawn (with crossings) in the plane in such a way that all the edges have equal length. That is, it is a unit distance graph.

The simplest non-orientable surface on which the Petersen graph can be embedded without crossings is the projective plane. This is the embedding given by the hemi-dodecahedron construction of the Petersen graph. The projective plane embedding can also be formed from the standard pentagonal drawing of the Petersen graph by placing a cross-cap within the five-point star at the center of the drawing, and routing the star edges through this cross-cap; the resulting drawing has six pentagonal faces. This construction shows that the Petersen graph has non-orientable genus 1.

Symmetries

The Petersen graph is strongly regular. It is also symmetric, meaning that it is edge transitive and vertex transitive. It is one of only 14 cubic distance-regular graphs. [According to [http://www.csse.uwa.edu.au/~gordon/remote/foster/#drgs Cubic symmetric graphs (The Foster Census)] .]

The automorphism group of the Petersen graph is the symmetric group $S\_5$; the action of $S\_5$ on the Petersen graph follows from its construction as a Kneser graph. Every homomorphism of the Petersen graph to itself that doesn't identify adjacent vertices is an automorphism. As shown in the figures, the drawings of the Petersen graph may exhibit five-way or three-way symmetry, but it is not possible to draw the Petersen graph in the plane in such a way that the drawing exhibits the full symmetry group of the graph.

Despite its high degree of symmetry, the Petersen graph is not a Cayley graph, and is the smallest connected vertex-transitive graph that is not a Cayley graph.

Hamiltonian paths and cycles

The Petersen graph has a Hamiltonian path but no Hamiltonian cycle. The following elegant proof due to D. West demonstrates that the Petersen graph is non-Hamiltonian. If there is a 10-cycle C, then the graph consists of C plus five chords. If each chord joins vertices opposite on C, then there is a 4-cycle. Hence some chord e joins vertices at distance 4 along C. Now no chord incident to a vertex opposite an endpoint of e on C can be added without creating a cycle with at most four vertices. Therefore, the Petersen graph is non-Hamiltonian. It is the smallest bridgeless cubic graph with no Hamiltonian cycle. It is hypohamiltonian, meaning that although it has no Hamiltonian cycle, deleting any vertex makes it Hamiltonian, and is the smallest hypohamiltonian graph.

The Petersen graph is one of only five known connected vertex transitive graphs with no Hamiltonian cycle; it is conjectured that there are no others. If "G" is a 2-connected, "r"-regular graph with at most 3"r" + 1 vertices, then "G" is Hamiltonian or "G" is the Petersen graph. [harvtxt|Holton|Sheehan|1993, page 32.]

Coloring

The Petersen graph has chromatic number 3, meaning that its vertices can be colored with three colors — but not with two — such that no edge connects vertices of the same color.

The Petersen graph has chromatic index 4; coloring the edges requires four colors. A proof of this requires checking four cases to demonstrate that no 3-edge-coloring exists. As a connected bridgeless cubic graph with chromatic index four, the Petersen graph is a snark. It is the smallest possible snark, and was the only known snark from 1898 until 1946. The snark theorem, a result conjectured by W. T. Tutte and announced in 2001 by Robertson, Sanders, Seymour, and Thomas, [citation|last=Pegg|first=Ed, Jr.|authorlink=Ed Pegg, Jr.|title=Book Review: The Colossal Book of Mathematics|journal=Notices of the American Mathematical Society|volume=49|issue=9|year=2002|pages=1084–1086|url=http://www.ams.org/notices/200209/rev-pegg.pdf.] states that every other snark has the Petersen graph as a minor.

Additionally, the graph has fractional chromatic index 3, proving that the difference between the chromatic index and fractional chromatic index can be as large as 1. The long-standing Goldberg-Seymour Conjecture proposes that this is the largest gap possible.

The Thue number (a variant of the chromatic index) of the Petersen graph is 5.

Other 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, has domination number 3, and has a perfect matching and a 2-factor. See the glossary.
* has radius 2 and diameter 2. It is the largest cubic graph with diameter 2.
* has graph spectrum −2, −2, −2, −2, 1, 1, 1, 1, 1, 3.
* 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.)
* has 2000 spanning trees, the most of any 10-vertex cubic graph. [harvtxt|Jakobson|Rivin|1999; harvtxt|Valdes|1991. The cubic graphs with 6 and 8 vertices maximizing the number of spanning trees are Möbius ladders.]

Generalized Petersen graphs

In 1950 H. S. M. Coxeter introduced a family of graphs generalizing the Petersen graph. These graphs are now called generalized Petersen graphs, a name given to them in 1969 by Mark Watkins. In Watkins' notation, "G"("n","k") is a graphwith vertex set

:{"u"₀, "u"₁, ..., "u"_"n"−1, "v"₀, "v"₁, ..., "v"_"n"−1}

and edge set

:{"u"_"i" "u"_"i"+1, "u"_"i" "v"_"i", "v"_"i" "v"_"i"+"k": "i" = 0,...,"n" − 1}

where subscripts are to be read modulo "n" and "k" < "n"/2. Coxeter's notation for the same graph would be {"n"}+{"n/k"}.

The Petersen graph itself is "G"(5,2) or {5}+{5/2}.

This family of graphs possesses a number of interesting properties. For example,
# "G"("n","k") is vertex-transitive if and only if "n" = 10 and "k" =2 or if "k"² ≡ ±1 (mod "n").
# 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). [harvtxt|Frucht|Graver|Wilkins|1971.] These seven graphs are therefore the only symmetric generalized Petersen graphs.
# It is bipartite if and only if "n" is even and "k" is odd.
# It is a Cayley graph if and only if "k"² ≡ ±1 (mod "n").
# It is hypohamiltonian when "n" is congruent to 5 modulo 6 and "k" is 2, "n"−2, ("n"+1)/2, or ("n"−1)/2 (all four of these choice of "k" lead to isomorphic graphs). It is also non-Hamiltonian when "n" is divisible by four, at least equal to 8, and "k" is "n"/2. In all other cases it has a Hamiltonian cycle harv|Alspach|1983.

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 harv|Castagna|Prins|1972.

Petersen graph family

The Petersen graph family consists of the seven graphs that can be formed from the complete graph $K\_6$ 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.

Notes

References

*citation
last1 = Alspach | first1 = B. R.
title = The classification of Hamiltonian generalized Petersen graphs
journal = Journal of Combinatorial Theory, Series B
volume = 34 | pages = 293–312 | year = 1983
id = MathSciNet | id = 0714452
doi = 10.1016/0095-8956(83)90042-4.
*.
*.
*citation
authorlink = Harold Scott MacDonald Coxeter
first = H. S. M. | last = Coxeter
title = Self-dual configurations and regular graphs
journal = Bulletin of the American Mathematical Society
volume = 56 | year = 1950 | pages = 413–455
doi = 10.1090/S0002-9904-1950-09407-5.
*citation
last1 = Frucht | first1 = R.
last2 = Graver | first2 = J. E.
last3 = Watkins | first3 = M. E.
title = The groups of the generalized Petersen graphs
journal = Proceedings of the Cambridge Philosophical Society
volume = 70 | year = 1971 | pages = 211–218.
*.
*citation
last1 = Jakobson | first1= Dmitry | last2= Rivin | first2= Igor
title = On some extremal problems in graph theory
year = 1999
id = arxiv|archive = math.CO|id = 9907050.
* Keller, Mitch. planetmath reference|id=5732|title=Kneser graphs
*.
*.
*citation
last = Valdes|first= L.
title = Extremal properties of spanning trees in cubic graphs
journal = Congressus Numerantium
year = 1991
volume = 85
pages = 143–160.
*.
*