Petersen-Graph

Der Petersen-Graph (benannt nach dem dänischen Mathematiker Julius Petersen) ist ein 3-regulärer (also kubischer) Graph mit 10 Knoten. Das bedeutet, dass jeder der Knoten drei Nachbarn hat, die Gradfolge ist also (3,3,3,3,3,3,3,3,3,3). Der Petersen-Graph ist in der Graphentheorie ein oft verwendetes Beispiel und Gegenbeispiel. Er tritt auch in der tropischen Geometrie auf.

Eigenschaften des Petersen-Graphen:

• Kubisch bzw. 3-regulär (per Definition)
• Nicht planar
• Zusammenhängend
• Symmetrisch
• Die Länge des kürzesten Kreises ist 5
• Enthält keinen Hamilton-Kreis
• Kleinster hypohamiltonscher Graph
• Chromatische Zahl (Graphentheorie) 3
• Chromatischer Index (Graphentheorie) 4
• Ist kein Cayley-Graph, obwohl er regulär und lokal-endlich ist.

Der Petersen-Graph gehört zu einer Gruppe von zusammenhängenden, brückenlosen und nicht planaren Graphen, die als „Snark“ bezeichnet werden.

Siehe auch: Typen von Graphen in der Graphentheorie in Graph (Graphentheorie)