Clebsch-Graph
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Clebsch_graph.svg/220px-Clebsch_graph.svg.png)
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
- 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
- Der Clebsch-Graph ist hamiltonsch.
- Die achromatische Zahl des Clebsch-Graphen ist .
- Die chromatische Zahl des Clebsch-Graphen ist .
- Der chromatische Index des Clebsch-Graphen ist .
Einzelnachweise
- ↑ 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.
- ↑ The Clebsch Graph. In: MathWorld. Abgerufen am 22. Oktober 2023 (englisch).