Petersen graph
From Free net encyclopedia
Image:Petersen graph.svg Image:Petersen graph, two crossings.svg Image:Petersen graph, unit distance.svg
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.<ref>The Petersen graph by Andries E. Brouwer.</ref> Although the graph is generally credited to Petersen, it had in fact first appeared 12 years earlier, in 1886.<ref>Template:Cite journal</ref>
Contents |
Properties
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.
Other properties
The Petersen graph ...
- is nonplanar. It has as minors both the complete graph <math>K_5</math> (contract the five short edges in the first picture), and the complete bipartite graph <math>K_{3,3}</math>.
- has crossing number 2.
- 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 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.<ref>According to Cubic symmetric graphs (The Foster Census).</ref>
- is the complement of the line graph of <math>K_5</math>.
- 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 <math>S_5</math>.
- is the Kneser graph <math>KG_{5,2}</math>. (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.
Every homomorphism of the Petersen graph to itself that doesn't identify adjacent vertices is an automorphism.
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 <math>(3,5)</math>-cage graph. In fact, since it has only 10 vertices, it is the unique <math>(3,5)</math>-Moore graph.)
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.<ref>Holton and Sheehan, page 32</ref>
Generalized Petersen graph
In 1969 Mark Watkins introduced a family of graphs generalizing the Petersen graph. The generalized Petersen graph <math>G(n,k)</math> is a graph with vertex set
- <math>\{u_0, u_1, \dots, u_{n-1}, v_0, v_1, \dots, v_{n-1}\}</math>
and edge set
- <math>\{u_i u_{i+1}, u_i v_i, v_i v_{i+k} : i=0,\dots,n-1\}</math>
where subscripts are to be read modulo <math>n</math> and <math>k < n/2</math>.
The Petersen graph itself is <math>G(5,2)</math>.
This family of graphs possesses a number of interesting properties. For example,
- <math>G(n,k)</math> is vertex-transitive if and only if <math>n = 10, k = 2</math> or <math>k^2 \equiv \pm 1 \pmod n</math>.
- It is edge-transitive only in the following seven cases: <math>(n,k) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5), (24,5) </math>.
- It is bipartite iff <math>n</math> is even and <math>k</math> is odd.
- It is a Cayley graph if and only if <math>k^2 \equiv 1 \pmod n</math>.
Among the generalized Petersen graphs are the n-prism <math>G(n,1)</math>, the Dürer graph <math>G(6,2)</math>, the Möbius-Kantor graph <math>G(8,3)</math>, the dodecahedron <math>G(10,2)</math>, and the Desargues graph <math>G(10,3)</math>.
The Petersen graph itself is the only generalized Petersen graph that is not 3-edge-colorable. [Castagna and Prins, 1972]
Petersen graph family
The Petersen graph family consists of the seven graphs that can be formed from the complete graph <math>K_6</math> 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 />