Petersen graph

Missing image
Petersen_graph.png
The Petersen graph
Missing image
Petersen_graph,_two_crossings.png
Another drawing of the Petersen graph, with only two crossings
Missing image
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.

Contents

Properties

Basic properties

The Petersen graph ...

Other properties

The Petersen graph ...

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,

  1. <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>.
  2. It is a Cayley graph if and only if <math>r^2 \equiv 1 \pmod n<math>.
  3. 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

External links

Navigation

  • Art and Cultures
    • Art (https://academickids.com/encyclopedia/index.php/Art)
    • Architecture (https://academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (https://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (https://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools