Shrikhandes Graph
| Shrikhandes Graph | |
|
Darstellung des Shrikhande-Graphen | |
| Anzahl der Scheitelpunkte | 16 |
|---|---|
| Anzahl Kanten | 48 |
| Abschlussverteilung | 6- regelmäßig |
| Strahl | 2 |
| Durchmesser | 2 |
| Gittergewebe | 3 |
| Automorphismen | 192 |
| Chromatische Zahl | 4 |
| Chromatischer Index | 6 |
| Eigenschaften |
Stark konsistenter Eulerscher Hamilton-Operator |
Der Shrikhande-Graph ist in der Graphentheorie ein 6-regulärer Graph mit 16 Ecken und 48 Kanten, der von SS Shrikhande entdeckt wurde .
Eigenschaften
Allgemeine Eigenschaften
Der Durchmesser des Shrikhande-Graphen, die maximale Exzentrizität seiner Scheitelpunkte, beträgt 2, sein Radius , die minimale Exzentrizität seiner Scheitelpunkte beträgt 2 und sein Netz , die Länge seines kürzesten Zyklus , ist 3. Er hat einen 6- Scheitelpunkt -verbundener Graph und eines 6- kantenverbundenen Graphen , dh er ist zusammenhängend und muss mindestens 6 Knoten oder 6 Kanten haben, um ihn getrennt zu machen.
Färbung
Die chromatische Zahl des Shrikhande-Graphen ist 4. Das heißt, es ist möglich, ihn mit 4 Farben so einzufärben, dass zwei durch eine Kante verbundene Ecken immer unterschiedliche Farben haben, aber diese Zahl ist minimal. Es gibt keine gültige 3-Färbung des Diagramms.
Der chromatische Index des Shrikhande-Graphen ist 6. Es gibt also eine 6-Färbung der Kanten des Graphen, so dass zwei Kanten, die auf denselben Scheitelpunkt fallen, immer unterschiedliche Farben haben. Diese Zahl ist minimal.
Algebraische Eigenschaften
Die Gruppe der Automorphismen des Shrikhande-Graphen hat die Ordnung 192.
Das charakteristische Polynom der Adjazenzmatrix des Shrikhande-Graphen ist: . Es lässt nur ganze Wurzeln zu. Shrikhandes Graph ist daher ein ganzzahliger Graph , ein Graph, dessen Spektrum aus ganzen Zahlen besteht.
Siehe auch
- (en) Eric W. Weisstein , „ Shrikhande Graph “ , auf MathWorld
- (de) Andries E. Brouwer , Shrikhande-Grafik
- (de) Peter Cameron , The Shrikhande Graph