Clebsch-Graph
# 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:

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

### 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$.
