Graphe de Perkel
Le graphe de Perkel est, en théorie des graphes, un graphe 6-régulier possédant 57 sommets et 171 arêtes. C'est l'unique graphe distance-régulier ayant pour vecteur d'intersection {6, 5, 2 ; 1, 1, 3}[1].
| Graphe de Perkel | |
 Neuf représentations du graphe de Perkel. | |
| Nombre de sommets | 57 |
|---|---|
| Nombre d'arêtes | 171 |
| Distribution des degrés | 6-régulier |
| Rayon | 3 |
| Diamètre | 3 |
| Maille | 5 |
| Automorphismes | 3 420 |
| Nombre chromatique | 3 |
| Propriétés | Distance-régulier Hamiltonien Sans triangle Sommet-transitif |
modifier  |
|
Construction
modifierLes sommets du graphe de Perkel peuvent être définis[2] comme les éléments du groupe abélien Z/3ZxZ/19Z où (i,j) est relié à (i+1,k) si (k-j)3 = 26i.
Propriétés
modifierPropriétés générales
modifierLe diamètre du graphe de Perkel, l'excentricité maximale de ses sommets, est 3, son rayon, l'excentricité minimale de ses sommets, est 3 et sa maille, la longueur de son plus court cycle, est 5. Il s'agit d'un graphe 6-sommet-connexe et d'un graphe 6-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre non connexe il faut le priver au minimum de 6 sommets ou de 6 arêtes.
Coloration
modifierLe nombre chromatique du graphe de Perkel est 3. C'est-à-dire qu'il est possible de le colorer avec 3 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 2-coloration valide du graphe.
Propriétés algébriques
modifierLe groupe d'automorphismes du graphe de Perkel est d'ordre 3 420.
Le polynôme caractéristique de la matrice d'adjacence du graphe de Perkel est : .
Références
modifier- ↑ (en) Kris Coolsaet et Jan Degraer, « A Computer Assisted Proof of the Uniqueness of the Perkel Graph », Designs, Codes and Crypt, no 34, , p. 155–171 (DOI /10.1007/s10623-004-4852-9).
- ↑ Andries E. Brouwer, Perkel graph
Lien externe
modifier(en) Eric W. Weisstein, « Perkel Graph », sur MathWorld
