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.

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.

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

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

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 ${\displaystyle K_{7}}$.

• Wolfram MathWorld: Heawood Graph