Petersen graph
|
|
Petersen_graph.png
Petersen_graph,_two_crossings.png
Petersen_graph_unit-distance.png
The Petersen graph is a small graph that serves as a useful example and counterexample in graph theory. It was first published by Julius Petersen in 1898.
| 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. See the glossary.
- 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.)
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 hypohamiltonian, meaning that although it has no Hamiltonian cycle, deleting any vertex makes it Hamiltonian.
- is one of only 14 cubic distance-regular graphs.
- is the complement of the line graph of <math>K_5<math>.
- is the only (connected) cubic graph of girth 5, making it the only <math>(3,5)<math>-cage graph and the only <math>(3,5)<math>-Moore graph.
- 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>K_{5,2}<math>.
- 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 largest cubic graph with diameter 2.
- is the smallest hypohamiltonian 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 (Holton page 32).
Generalized Petersen graph
The generalized Petersen graph <math>G(n,k)<math> is a graph with vertex set <math>
V(G(n,k)) = \{u_0,u_1,\dots,u_{n-1},v_0,v_1,\dots,v_{n-1}\}
<math>
and edge set <math>
E(G(n,k)) = \{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 important and well known family of graphs that was introduced in 1969 by Mark Watkins possesses a number of interesting properties. For example,
- <math>G(n,r)<math> is vertex-transitive if and only if <math>n = 10, r = 2<math> or <math>r^2 \equiv \pm 1 \pmod n<math>.
- It is a Cayley graph if and only if <math>r^2 \equiv 1 \pmod n<math>.
- It is arc-transitive only in the following seven cases: <math>(n,r) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5), (24,5) <math>.
The family contains some very important graphs. Among others 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>, the Desargues graph <math>G(10,3)<math>, etc.
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 delta-Y or Y-delta transforms. A graph is intrinsically linked if and only if it contains one of these graphs as a subgraph.
References
- Template:Journal reference
- Template:Book reference Available on Google print (http://print.google.com/print?id=nld40slgtdkC&lpg=1&prev=http://print.google.com/print%3Fq%3DPetersen%2BGraph&pg=0_1&sig=9I_4mnnsjsU8nWaAW5O5SbeobYY).
- Mitch Keller, Template:Planetmath reference
- Template:Book reference
- Template:Journal reference
- Template:MathWorld
External links
- Cubic symmetric graphs (The Foster Census) (http://www.csse.uwa.edu.au/~gordon/remote/foster/#drgs)
- The Petersen graph (http://www.win.tue.nl/~aeb/drg/graphs/Petersen.html) by Andries E. Brouwerde:Petersen-Graph