Accueil🇫🇷Chercher

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
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

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

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.