Clebsch-Graph

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Clebsch graph.svg

In der Graphentheorie ist der Clebsch-Graph ein ungerichteter Graph mit 16 Knoten und 40 Kanten. Er ist benannt nach Alfred Clebsch, der ihn 1868 betrachtete. Die Bezeichnung Greenwood–Gleason-Graph wird dazu synonym verwendet.[1][2]

Der Graph kann wie folgt konstruiert werden: Die Knoten v_i\in V des fünfdimensionalen Würfels seien Binärdarstellungen der festen Länge 5 der ganzen Zahlen von 0 bis 2^5-1=31, also die Zeichenfolgen:

v_0= "00000" → 0
v_1= "00001" → 1
v_2= "00010" → 2
...
v_{31}= "11111" → 31

Die Kantenmenge des Würfels ist dann die Relation A\subset V\times V mit (x,y)\in A \Leftrightarrow x und y unterscheiden sich in genau einer Stelle ihrer Darstellungen. Daraus erhält man den Clebsch-Graphen durch Identifikation antipodaler Eckpunkte, also Punkten, die sich in allen 5 Stellen unterscheiden.

Eigenschaften[Bearbeiten]

Graphentheoretische Eigenschaften

Der Graph ist stark regulär. Der Minimalgrad und der Maximalgrad sind gleich und haben den Wert 5, also ist der Graph nicht eulersch. Der Graph ist hamiltonsch und nicht planar. Der Komplementgraph ist ebenfalls stark regulär.

Algebraische Eigenschaften

Der Graph ist ein Cayleygraph. Seine Automorphismengruppe hat die Ordnung 1920 und ist isomorph zur Coxeter-Gruppe D_5. Der Graph ist knoten-, kanten- und distanztransitiv.

Planare Einbettungen[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. A. Clebsch, Ueber die Flächen vierter Ordnung, welche eine Doppelcurve zweiten Grades besitzen, J. für Math. 69 (1868) 142-184.
  2. The Clebsch Graph bei Mathworld