Graphe de Gewirtz
| Graphe de Gewirtz | |
 Représentations du graphe de Gewirtz. | |
| Nombre de sommets | 56 |
|---|---|
| Nombre d'arêtes | 280 |
| Distribution des degrés | 10-régulier |
| Rayon | 2 |
| Diamètre | 2 |
| Maille | 4 |
| Automorphismes | 80 640 |
| Nombre chromatique | 4 |
| Propriétés | Hamiltonien Intégral |
modifier  |
|
Le graphe de Gewirtz (ou graphe de Sims-Gewirtz) est, en théorie des graphes, un graphe 10-régulier possédant 56 sommets et 280 arêtes. Il doit son nom à Allan Gewirtz, qui le décrivit dans sa thèse en 1967[1].
Propriétés modifier
Propriétés générales modifier
Le diamètre du graphe de Gewirtz, 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. Il s'agit d'un graphe 10-sommet-connexe et d'un graphe 10-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 10 sommets ou de 10 arêtes.
Coloration modifier
Le nombre chromatique du graphe de Gewirtz 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.
Le complémentaire du graphe de Gewirtz a un nombre chromatique égal à 28.
Propriétés algébriques modifier
Le groupe d'automorphismes du graphe de Gewirtz est un groupe d'ordre 80 640.
Le polynôme caractéristique de la matrice d'adjacence du graphe de Gewirtz est : . Ce polynôme caractéristique n'admet que des racines entières. Le graphe de Gewirtz est donc un graphe intégral, un graphe dont le spectre est constitué d'entiers.
Voir aussi modifier
Liens internes modifier
Liens externes modifier
Références modifier
- Allan Gewirtz, Graphs with Maximal Even Girth, Ph.D. Dissertation in Mathematics, City University of New York, 1967.
