Graphe de Harries

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Graphe de Harries
Image illustrative de l'article 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

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[modifier | modifier le code]

Propriétés générales[modifier | modifier le code]

Le graphe de Harries est une (3,10)-cage, c'est-à-dire un graphe minimal en nombres de sommets ayant une maille de 10 et étant régulier de degrés 3. La première cage de ce type à avoir été découverte est la 10-cage de Balaban, dont la description fut publiée en 1972[1]. La liste complète des (3-10)-cages a été donnée par O'Keefe et Wong en 1980[2]. Il en existe trois distinctes, les deux autres étant le graphe de Harries-Wong et la 10-cage de Balaban sus-citée[3].

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. Comme il est régulier de degrés 3 ce nombre est optimal. Le graphe de Harries est donc un graphe optimalement connecté.

Coloration[modifier | modifier le code]

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 telle que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes. Ce nombre est minimal.

Propriétés algébriques[modifier | modifier le code]

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

Le polynôme caractéristique de la matrice d'adjacence du graphe de Harries est : (x-3) (x-1)^4 (x+1)^4 (x+3) (x^2-6) (x^2-2) (x^4-6x^2+2)^5 (x^4-6x^2+3)^4 (x^4-6x^2+6)^5.

Représentations[modifier | modifier le code]

Voir aussi[modifier | modifier le code]

Liens internes[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Références[modifier | modifier le code]

  1. (en) A. T. Balaban, A trivalent graph of girth ten, J. Combinatorial Theory, Set. B, 12:1-5, 1972
  2. (en) M. O'Keefe et P.K. Wong, A smallest graph of girth 10 and valency 3, J. Combin. Theory Ser. B 29 (1980) 91-105.
  3. (en) J. A. Bondy et U. S. R. Murty, Graph Theory with Applications. New York: North Holland, p. 237, 1976.