Petersen graph: Difference between revisions

Browse history interactively

← Previous edit Next edit →

Content deleted Content added

VisualWikitext

Inline

Revision as of 01:57, 7 March 2005

File:Petersen graph, two crossings.png

Another drawing of the Petersen graph, with only two crossings

File:Petersen graph unit-distance.png

Another drawing, with each edge the same length

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.

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, since it has the complete graph $K_{5}$ as a minor (contract the five short edges in the first picture).
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 $K_{5}$ .
is the only (connected) cubic graph of girth 5, making it the only $(3,5)$ -cage graph and the only $(3,5)$ -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 $S_{5}$ .
is the Kneser graph $K_{5,2}$ .
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 $G(n,k)$ is a graph with vertex set $V(G(n,k))=\{u_{0},u_{1},\dots ,u_{n-1},v_{0},v_{1},\dots ,v_{n-1}\}$ and edge set $E(G(n,k))=\{u_{i}u_{i+1},u_{i}v_{i},v_{i}v_{i+k}:i=0,\dots ,n-1\}.$ where subscripts are to be read modulo $n$ and $k<n/2$ . The Petersen graph itself is $G(5,2)$ . This important and well known family of graphs that was introduced in 1969 by Mark Watkins possesses a number of interesting properties. For example,

 $G(n,r)$  is vertex transitive if and only if

$n=10,r=2$ or $r^{2}\equiv \pm 1{\pmod {n}}$ .

It is a Cayley graph if and only if  $r^{2}\equiv 1{\pmod {n}}$ .
It is arc-transitive only in the following seven cases:

$(n,r)=(4,1),(5,2),(8,3),(10,2),(10,3),(12,5),(24,5)$ .

The family contains some very important graphs. Among others 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)$ , the Desargues graph $G(10,3)$ , etc.

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 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
. ISBN 0521435943. {{cite book}}: Missing or empty |title= (help); Unknown parameter |Author= ignored (|author= suggested) (help); Unknown parameter |Publisher= ignored (|publisher= suggested) (help); Unknown parameter |Title= ignored (|title= suggested) (help); Unknown parameter |Year= ignored (|year= suggested) (help) Available on Google print.
Mitch Keller, "Kneser graphs". PlanetMath.
. ISBN 0-444-81504-X. {{cite book}}: Missing or empty |title= (help); Unknown parameter |Author= ignored (|author= suggested) (help); Unknown parameter |Publisher= ignored (|publisher= suggested) (help); Unknown parameter |Title= ignored (|title= suggested) (help); Unknown parameter |Year= ignored (|year= suggested) (help)
Template:Journal reference
Weisstein, Eric W. "Petersen Graph". MathWorld.

External links

Cubic symmetric graphs (The Foster Census)
The Petersen graph by Andries E. Brouwer

@@ Line 42: / Line 42: @@
 The Petersen graph frequently arises as a counterexample or exception in graph theory.  For example, if <math>G</math> is a 2-connected, <math>r</math>-regular graph with at most <math>3r+1</math> vertices, then <math>G</math> is Hamiltonian or <math>G</math> 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 <math>n</math>-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 ==