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

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

Liens externes

Références

    • Portail des mathématiques
    Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.