Graphe de Higman-Sims
| Graphe de Higman-Sims | |
 Représentation du graphe de Higman-Sims | |
| Nombre de sommets | 100 |
|---|---|
| Nombre d'arêtes | 1100 |
| Distribution des degrés | 22-régulier |
| Rayon | 2 |
| Diamètre | 2 |
| Maille | 4 |
| Automorphismes | 88 704 000 |
| Propriétés | Fortement régulier Eulérien Hamiltonien |
modifier  |
|
Le graphe de Higman-Sims est, en théorie des graphes, un graphe 22-régulier possédant 100 sommets et 1100 arêtes.
Propriétés modifier
Propriétés générales modifier
Le diamètre du graphe de Higman-Sims, 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 4. Il s'agit d'un graphe 22-sommet-connexe et d'un graphe 22-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 22 sommets ou de 22 arêtes.
Propriétés algébriques modifier
Le groupe d'automorphismes du graphe de Higman-Sims est un groupe d'ordre 88 704 000. Il est isomorphe au produit semi-direct du groupe de Higman-Sims d'ordre 44 352 000 avec le groupe cyclique d'ordre 2[1]. Il agit transitivement sur l'ensemble des arêtes du graphe de Higman-Sims, faisant de lui un graphe arête-transitif, c'est-à-dire un graphe dont toutes les arêtes jouent exactement le même rôle[2].
Le polynôme caractéristique de la matrice d'adjacence du graphe de Higman-Sims est : . Le graphe de Higman-Sims est donc un graphe intégral, un graphe dont le spectre est constitué d'entiers.
Notes et références modifier
- (en) Andries Brouwer, « Higman-Sims graph »
- (en) A. E. Brouwer et W. H. Haemers, « The Gewirtz Graph: An Exercise in the Theory of Graph Spectra », dans Euro. J. Combin., vol. 14, 1993, p. 397-407
Voir aussi modifier
Liens externes modifier
(en) Eric W. Weisstein, « Higman-Sims Graph », sur MathWorld
