Graphe de Brouwer-Haemers

Le graphe de Brouwer-Haemers est, en théorie des graphes, un graphe 20-régulier possédant 81 sommets et 810 arêtes. C'est plus précisément un graphe fortement régulier de paramètres (81,20,1,6).

Graphe de Brouwer-Haemers
Représentations du graphe de Brouwer-Haemers.
Nombre de sommets	81
Nombre d'arêtes	810
Distribution des degrés	20-régulier
Rayon	2
Diamètre	2
Maille	3
Automorphismes	233 280
Nombre chromatique	7
Propriétés	Fortement régulier Hamiltonien
modifier

Propriétés

Propriétés générales

Le diamètre du graphe de Brouwer-Haemers, 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 3. Il s'agit d'un graphe 20-sommet-connexe et d'un graphe 20-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 20 sommets ou de 20 arêtes.

Coloration

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

Propriétés algébriques

Le groupe d'automorphismes du graphe de Brouwer-Haemers est un groupe d'ordre 233 280.

Le polynôme caractéristique de la matrice d'adjacence du graphe de Brouwer-Haemers est : ${\displaystyle -(x-20)(x-2)^{60}(x+7)^{20}}$. Il n'admet que des racines entières. Le graphe de Brouwer-Haemers est donc un graphe intégral, un graphe dont le spectre est constitué d'entiers.

Voir aussi

Liens internes

• Théorie des graphes

Liens externes

• (en) Eric W. Weisstein, Brouwer-Haemers Graph (MathWorld)
• (en) Andries E. Brouwer, Brouwer-Haemers graph

Références

• Portail des mathématiques