Heawood-Graph

Heawood graph

In der Mathematik ist der Heawood-Graph ein Graph mit 14 Knoten und 21 Kanten, der unter anderem als Inzidenzgraph der Fano-Ebene von Bedeutung ist. Er ist nach Percy Heawood benannt.

Kombinatorische Eigenschaften

Der Heawood-Graph ist bipartit und deshalb mit 2 Farben färbbar.

Der Heawood-Graph ist ein kubischer Graph, d. h. 3-regulär.

Er ist bipartit und hat deshalb die chromatische Zahl 2.

Er hat Durchmesser 3 und ist der einzige kubische Graph, der keinen Zykel der Länge 5 enthält.

Symmetrien

Die Automorphismengruppe des Heawood-Graphen ist isomorph zur projektiven linearen Gruppe $PGL(2,F_{7})$ und hat demzufolge 336 Elemente.

Der Heawood-Graph ist abstandstransitiv, d. h. zu je zwei Punktpaaren $(x,y),(u,v)$ mit $d(x,y)=d(u,v)$ gibt es einen Automorphismus, der $x$ auf $u$ und $y$ auf $v$ abbildet.

Der Heawood-Graph in Geometrie und Topologie

Diese Einbettung des Heawood-Graphen zerlegt den Torus (der durch Identifikation gegenüberliegender Quadrat-Kanten entsteht) in 7 Regionen.

Der Heawood-Graph ist der Inzidenzgraph der Fano-Ebene.

Er kann kreuzungsfrei in den Torus eingebettet werden, den er in 7 sich paarweise berührende Regionen zerlegt. Insbesondere ist er dual zum vollständigen Graphen $K_{7}$.

Weblinks

• Wolfram MathWorld: Heawood Graph