Graphe de Harries

Graphe de Harries
Représentation du graphe de Harries.
Nombre de sommets	70
Nombre d'arêtes	105
Rayon	6
Diamètre	6
Maille	10
Automorphismes	120 (S5)
Nombre chromatique	2
Indice chromatique	3
Propriétés	Cubique Cage Sans triangle Hamiltonien
modifier

Le graphe de Harries est, en théorie des graphes, un graphe régulier possédant 70 sommets et 105 arêtes.

Propriétés

Propriétés générales

Le diamètre du graphe de Harries, l'excentricité maximale de ses sommets, est 6, son rayon, l'excentricité minimale de ses sommets, est 6 et sa maille, la longueur de son plus court cycle, est 10. Il s'agit d'un graphe 3-sommet-connexe et d'un graphe 3-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 3 sommets ou de 3 arêtes.

Coloriage

Le nombre chromatique du graphe de Harries est 2. C'est-à-dire qu'il est possible de le colorer avec 2 couleurs de telle façon que deux sommets reliés par une arête soient toujours de couleurs différentes. Ce nombre est minimal.

L'indice chromatique du graphe de Harries est 3. Il existe donc une 3-coloration des arêtes du graphe tels que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes. Ce nombre est minimal.

Propriétés algébriques

Le groupe d'automorphismes du graphe de Harries est un groupe d'ordre 120 et est isomorphe au groupe symétrique S₅.

Le polynôme caractéristique du graphe de Harries est : (x − 3)(x − 1)⁴(x + 1)⁴(x + 3)(x² − 6)(x² − 2)(x⁴ − 6x² + 2)⁵(x⁴ − 6x² + 3)⁴(x⁴ − 6x² + 6)⁵.

Représentations

• 

  Représentation du nombre chromatique du graphe de Harries : 2.

• 

  Représentation de l'indice chromatique du graphe de Harries : 3

• 

  Représentation alternative du graphe.

Voir aussi

Liens internes

• Théorie des graphes
• Cage (théorie des graphes)

Liens externes

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

Références

• Portail des mathématiques