Graphe de Clebsch

Le graphe de Clebsch est hamiltonien.

Le graphe de Clebsch est un graphe fortement régulier de paramètres ${\displaystyle (v,k,\lambda ,\mu )=(16,5,0,2)}$[3] - [4].

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

Le graphe de Clebsch est également un graphe non-planaire, un graphe non-eulérien et un hamiltonien.

Le nombre chromatique du graphe de Clebsch est 4. C'est-à-dire qu'il est possible de le colorer avec 4 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 3-coloration valide du graphe.

L'indice chromatique du graphe de Clebsch est 5. Il existe donc une 5-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.

• 
  Le nombre achromatique du graphe de Clebsch est 8.
• 
  Le nombre chromatique du graphe de Clebsch est 4.
• 
  L'indice chromatique du graphe de Clebsch est 5.

Le groupe d'automorphismes du graphe de Clebsch est d'ordre 1 920. Il est isomorphe au groupe de Coxeter D₅. Ce groupe d'automorphismes agit transitivement sur l'ensemble des sommets du graphe de Clebsch, faisant de lui un graphe sommet-transitif[5].

Le polynôme caractéristique de la matrice d'adjacence du graphe de Clebsch est : ${\displaystyle (x-5)(x-1)^{10}(x+3)^{5}}$. Il n'admet que des racines entières. Le graphe de Clebsch est donc un graphe intégral, un graphe dont le spectre est constitué d'entiers[5].

Le graphe complémentaire du graphe de Clebsch est un graphe 10-régulier. Il est lui aussi fortement régulier[5]. Il s'agit du graphe demi-hypercube construit à partir de l'hypercube en 5 dimensions (penteract). Pour le construire, on relie les sommets qui sont à une distance 2 dans l'hypercube ; cela donne deux graphes isomorphes dont on ne garde que l'un des deux.

C'est ce graphe 10-régulier, à 16 sommets et à 80 arêtes que certains auteurs comme J. J. Seidel (en 1968) ou Andries Brouwer appellent « graphe de Clebsch »[6] - [7]. Le graphe décrit par Clebsch un siècle plus tôt, dans son article de 1868, est néanmoins bien le graphe 5-régulier[1].

Soit ${\displaystyle v}$ un sommet quelconque du graphe de Clebsch. Le sous-graphe induit aux 10 sommets qui ne sont pas des voisins de ${\displaystyle v}$ est le graphe de Petersen.

• Théorie des graphes

• (en) Eric W. Weisstein, « Clebsch Graph », sur MathWorld