Graphe de Hall-Janko

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

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

Zvonimir Janko (de) (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 (en) 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[modifier | modifier le code]

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

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

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

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.

Liens externes[modifier | modifier le code]