Graphe de Gewirtz

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Graphe de Gewirtz
Image illustrative de l'article 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

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.

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]

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