Graphe de Perkel

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	Hamiltonien Sans triangle Sommet-transitif
modifier

Le graphe de Perkel est, en théorie des graphes, un graphe 6-régulier possédant 57 sommets et 171 arêtes.

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^6i[1].

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 déconnecté il faut le priver au minimum de 6 sommets ou de 6 arêtes.

Coloriage

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 mais 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 un d'ordre 3 420.

Le polynôme caractéristique du graphe de Perkel est : − (x − 6)(x + 3)²⁰(x² − 3x + 1)¹⁸.

Voir aussi

Liens internes

• Théorie des graphes

Liens externes

• (en) Eric W. Weisstein, Perkel Graph (MathWorld)

Références

• Portail des mathématiques