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 : $(x-10)(x-2)^{35}(x+4)^{20}$ . 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.