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

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.

Coloriage

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 du graphe de Gewirtz est : (x − 10)(x − 2)³⁵(x + 4)²⁰. 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

• Théorie des graphes

Liens externes

• (en) Eric W. Weisstein, Gewirtz Graph (MathWorld)
• (en) Andries E. Brouwer, Sims-Gewirtz graph

Références

1. ↑ Allan Gewirtz, Graphs with Maximal Even Girth, Ph.D. Dissertation in Mathematics, City University of New York, 1967.