Clebsch-Graph

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.

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\iff 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 fünf Stellen unterscheiden.

Eigenschaften

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

• 
  Der Clebsch-Graph ist hamiltonsch.
• 
  Die achromatische Zahl des Clebsch-Graphen ist $8$.
• 
  Die chromatische Zahl des Clebsch-Graphen ist $4$.
• 
  Der chromatische Index des Clebsch-Graphen ist $5$.