Graphe de Perkel

Modèle:Infobox Graphe 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}.

Construction

Les sommets du graphe de Perkel peuvent être définis comme les éléments du groupe abélien Z/3ZxZ/19Z où (i,j) est relié à (i+1,k) si (k-j)³ = 2⁶ⁱ.

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 : $-(x-6)(x+3{)}^{20}(x^2-3x+1{)}^{18}$.