Graphe de Brouwer-Haemers
Le graphe de Brouwer-Haemers est, en théorie des graphes, un graphe 20-régulier possédant 81 sommets et 810 arêtes. C'est plus précisément un graphe fortement régulier de paramètres (81,20,1,6).
| Graphe de Brouwer-Haemers | |
 Représentations du graphe de Brouwer-Haemers. | |
| Nombre de sommets | 81 |
|---|---|
| Nombre d'arêtes | 810 |
| Distribution des degrés | 20-régulier |
| Rayon | 2 |
| Diamètre | 2 |
| Maille | 3 |
| Automorphismes | 233 280 |
| Nombre chromatique | 7 |
| Propriétés | Fortement régulier Hamiltonien |
modifier  |
|
Propriétés modifier
Propriétés générales modifier
Le diamètre du graphe de Brouwer-Haemers, 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 20-sommet-connexe et d'un graphe 20-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 20 sommets ou de 20 arêtes.
Coloration modifier
Le nombre chromatique du graphe de Brouwer-Haemers est 7. C'est-à-dire qu'il est possible de le colorer avec 7 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 6-coloration valide du graphe.
Propriétés algébriques modifier
Le groupe d'automorphismes du graphe de Brouwer-Haemers est un groupe d'ordre 233 280.
Le polynôme caractéristique de la matrice d'adjacence du graphe de Brouwer-Haemers est : . Il n'admet que des racines entières. Le graphe de Brouwer-Haemers est donc un graphe intégral, un graphe dont le spectre est constitué d'entiers.
Voir aussi modifier
Liens internes modifier
Liens externes modifier
- (en) Eric W. Weisstein, Brouwer-Haemers Graph (MathWorld)
- (en) Andries E. Brouwer, Brouwer-Haemers graph
