Graphe de Brouwer-Haemers

	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

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).

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

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

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

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

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

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

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

Coloration[modifier | modifier le code]

Propriétés algébriques[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]