Graphe de Gewirtz
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].
| 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 |
Propriétés
Propriétés générales
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
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
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
Liens internes
Liens externes
Références
- Allan Gewirtz, Graphs with Maximal Even Girth, Ph.D. Dissertation in Mathematics, City University of New York, 1967.