Graphe de Schläfli
| Graphe de Schläfli | |
 Représentation du graphe de Schläfli. | |
| Nombre de sommets | 27 |
|---|---|
| Nombre d'arêtes | 216 |
| Distribution des degrés | 16-régulier |
| Rayon | 2 |
| Diamètre | 2 |
| Maille | 3 |
| Automorphismes | 51 840 |
| Nombre chromatique | 9 |
| Propriétés | Fortement régulier Eulérien Hamiltonien |
modifier  |
|
Le graphe de Schläfli est, en théorie des graphes, un graphe 16-régulier possédant 27 sommets et 216 arêtes. C'est plus précisément un graphe fortement régulier de paramètres (27,16,10,8).
Propriétés
[modifier | modifier le code]Propriétés générales
[modifier | modifier le code]Le diamètre du graphe de Schläfli, l'excentricité maximale de ses sommets, est 2, son rayon, l'excentricité minimale de ses sommets, est 2 et sa maille, la longueur de son plus court cycle, est 3. Il s'agit d'un graphe 16-sommet-connexe et d'un graphe 16-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 16 sommets ou de 16 arêtes.
Coloration
[modifier | modifier le code]Le nombre chromatique du graphe de Schläfli est 9. C'est-à-dire qu'il est possible de le colorer avec 9 couleurs de telle façon que deux sommets reliés par une arête soient toujours de couleurs différentes mais ce nombre est minimal. Il n'existe pas de 8-coloration valide du graphe.
Propriétés algébriques
[modifier | modifier le code]Le groupe d'automorphismes du graphe de Schläfli est d'ordre 51 840.
Le polynôme caractéristique de la matrice d'adjacence du graphe de Schläfli est : . Ce polynôme caractéristique n'admet que des racines entières. Le graphe de Schläfli est donc un graphe intégral, un graphe dont le spectre est constitué d'entiers.
Voir aussi
[modifier | modifier le code]Liens internes
[modifier | modifier le code]Liens externes
[modifier | modifier le code]- (en) Eric W. Weisstein, Schläfli Graph (MathWorld)
- (en) Andries E. Brouwer, Schläfli graph
