Graphe tronqué de Witt

Graphe tronqué de Witt
Nombre de sommets	506
Nombre d'arêtes	3 795
Distribution des degrés	15-régulier
Rayon	3
Diamètre	3
Maille	5
Automorphismes	10 200 960
Propriétés	Régulier Hamiltonien
modifier

Le graphe tronqué de Witt est, en théorie des graphes, un graphe 15-régulier possédant 506 sommets et 3 795 arêtes.^[1]

Propriétés

Propriétés générales

Le diamètre du graphe tronqué de Witt, l'excentricité maximale de ses sommets, est 3, son rayon, l'excentricité minimale de ses sommets, est 3 et sa maille, la longueur de son plus court cycle, est 5. Il s'agit d'un graphe 15-sommet-connexe et d'un graphe 15-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 15 sommets ou de 15 arêtes.

Propriétés algébriques

Le groupe d'automorphismes du graphe tronqué de Witt est d'ordre 10 200 960. Il est isomorphe au groupe sporadique M₂₃, un des cinq groupes de Mathieu, et fournit donc une construction alternative de ce groupe.

Le polynôme caractéristique du graphe tronqué de Witt est : (x − 15)(x − 4)²³⁰(x + 3)²⁵³(x + 8)²². Ce polynôme caractéristique n'admet que des racines entières. Le graphe tronqué de Witt est donc un graphe intégral, un graphe dont le spectre est constitué d'entiers. Il est également déterminé de façon unique par son spectre de graphe^[2].

Voir aussi

Liens internes

• Théorie des graphes

Liens externes

• (en) Eric W. Weisstein, Truncated Witt Graph (MathWorld)

Références

1. ↑ Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. "The Truncated Witt Graph Associated to M₂₃." §11.4B in Distance Regular Graphs. New York: Springer-Verlag, pp. 367-368, 1989.
2. ↑ van Dam, E. R. and Haemers, W. H. "Which Graphs Are Determined by Their Spectrum?" Lin. Algebra Appl. 373, 139-162, 2003.