Graphe de Hall-Janko
Le graphe de Hall-Janko est, en théorie des graphes, un graphe 36-régulier possédant 100 sommets et 1 800 arêtes. C'est un graphe fortement régulier de type (100, 36, 14, 12).
| graphe de Hall-Janko | |
 Représentation du graphe de Hall-Janko | |
| Nombre de sommets | 100 |
|---|---|
| Nombre d'arêtes | 1800 |
| Distribution des degrés | 36-régulier |
| Rayon | 2 |
| Diamètre | 2 |
| Maille | 3 |
| Automorphismes | 1 209 600 |
| Nombre chromatique | 10 |
| Propriétés | Fortement régulier Eulérien Hamiltonien Cayley |
Histoire
Zvonimir Janko (né en 1932) est un mathématicien croate à l'origine de la théorie des groupes sporadiques.
Le graphe Hall-Janko a permis à Marshall Hall et David B. Wales de démontrer l'existence du groupe de Janko J2 ou « groupe de Hall-Janko » prévu par Janko, en le réalisant comme sous-groupe d'indice 2 du groupe des automorphismes de ce graphe.
Propriétés
Propriétés générales
Le diamètre du graphe de Hall-Janko (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 36-sommet-connexe et d'un graphe 36-arête-connexe, c'est-à -dire qu'il est connexe et que pour le rendre non connexe il faut le priver au minimum de 36 sommets ou de 36 arêtes.
Coloration
Le nombre chromatique du graphe de Hall-Janko est 10, c'est-à -dire qu'il est possible de le colorer avec 10 couleurs de telle façon que deux sommets reliés par une arête soient toujours de couleurs différentes et que ce nombre est minimal : il n'existe pas de 9-coloration valide du graphe.
Propriétés algébriques
Le groupe d'automorphismes du graphe de Hall-Janko est d'ordre 1 209 600.
Le polynôme caractéristique de la matrice d'adjacence du graphe de Hall-Janko est : . Le graphe de Hall-Janko est donc un graphe intégral, un graphe dont le spectre est constitué d'entiers.
Liens externes
- (en) Eric W. Weisstein, « Hall-Janko Graph », sur MathWorld
- (en) Andries E. Brouwer, Hall-Janko graph