Graphe de Hall-Janko
# 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).

## 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 $J_2$ 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 : $(x-36)(x-6)^{36}(x+4)^{63}$. Le graphe de Hall-Janko est donc un graphe intégral, un graphe dont le spectre est constitué d'entiers.

