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