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 des fünfdimensionalen Würfels seien Binärdarstellungen der festen Länge der ganzen Zahlen von bis , also die Zeichenfolgen:

 "00000" → 0
 "00001" → 1
 "00010" → 2
…
 "11111" → 31

Die Kantenmenge des Würfels ist dann die Relation mit und 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 fünf Stellen unterscheiden.

Eigenschaften

Bearbeiten
Graphentheoretische Eigenschaften

Der Graph ist stark regulär. Der Minimalgrad und der Maximalgrad sind gleich und haben den Wert  , 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   und ist isomorph zur Coxeter-Gruppe  . Der Graph ist knoten-, kanten- und distanztransitiv.

Planare Einbettungen

Bearbeiten

Einzelnachweise

Bearbeiten
  1. Alfred Clebsch: Ueber die Flächen vierter Ordnung, welche eine Doppelcurve zweiten Grades besitzen. In: Journal für Mathematik. Band 69, 1868, S. 142–184.
  2. The Clebsch Graph. In: MathWorld. Abgerufen am 22. Oktober 2023 (englisch).