Graphe de Higman-Sims

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
graphe de Higman-Sims
Image illustrative de l'article 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

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 | modifier le code]

Propriétés générales[modifier | modifier le code]

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 | modifier le code]

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 (en), 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 : (x-22)(x-2)^{77}(x+8)^{22}. Le graphe de Higman-Sims est donc un graphe intégral, un graphe dont le spectre est constitué d'entiers.

Références[modifier | modifier le code]

  1. (en) Andries Brouwer, « Higman-Sims graph »
  2. (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

Lien externe[modifier | modifier le code]

(en) Eric W. Weisstein, « Higman-Sims Graph », MathWorld