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 |
Construction
Les 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
Propriétés générales
Le 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
Le 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
Le 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
- Coolsaet, K. and Degraer, J. "A Computer Assisted Proof of the Uniqueness of the Perkel Graph." Designs, Codes and Crypt. 34, 155–171, 2005.
- Andries E. Brouwer, Perkel graph
Lien externe
(en) Eric W. Weisstein, « Perkel Graph », sur MathWorld