Graphe de Harborth

Le diamètre du graphe de Harborth, l'excentricité maximale de ses sommets, est 9, son rayon, l'excentricité minimale de ses sommets, est 6 et sa maille, la longueur de son plus court cycle, est 3. Il s'agit d'un graphe 3-sommet-connexe et d'un graphe 4-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 4 arêtes.

En 2006, Eberhard H.-A. Gerbracht démontra que c'était un graphe rigide[3].

Le nombre chromatique du graphe de Harborth 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.

L'indice chromatique du graphe de Harborth est 4. Il existe donc une 4-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 groupe d'automorphismes du 52-graphe de Harborth est un groupe abélien d'ordre 4 isomorphe à Z/2Z×Z/2Z, le groupe de Klein.

Le polynôme caractéristique de la matrice d'adjacence du graphe de Harborth est :

${\displaystyle (x-4)(x+2)^{6}(x^{11}-4x^{10}-14x^{9}+50x^{8}+89x^{7}-196x^{6}-293x^{5}+214x^{4}+351x^{3}+10x^{2}-69x-14)}$

${\displaystyle (x^{11}-2x^{10}-18x^{9}+26x^{8}+111x^{7}-94x^{6}-267x^{5}+72x^{4}+213x^{3}-47x-4)}$

${\displaystyle (x^{11}-18x^{9}-14x^{8}+99x^{7}+136x^{6}-135x^{5}-290x^{4}-27x^{3}+166x^{2}+93x+14)}$

${\displaystyle (x^{12}-2x^{11}-22x^{10}+26x^{9}+181x^{8}-74x^{7}-641x^{6}-120x^{5}+863x^{4}+532x^{3}-153x^{2}-152x-16)}$

• Théorie des graphes

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