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 Propriétés générales 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 Le groupe d'automorphismes du graphe de Higman-Sims est un groupe d'ordre . Il est isomorphe au produit semi-direct du groupe de Higman-Sims d'ordre avec le groupe cyclique d'ordre 2. 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 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, .
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
Voir aussi Liens externes
Higman-Sims