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 Intégral |
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[modifier | modifier le code]
Propriétés générales[modifier | modifier le code]
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[modifier | modifier le code]
Le groupe d'automorphismes du graphe tronqué de Witt est d'ordre 10 200 960. Il est isomorphe au groupe sporadique un des cinq groupes de Mathieu, ce qui fournit donc une construction possible de ce groupe.
Le polynôme caractéristique de la matrice d'adjacence du graphe tronqué de Witt est : . 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[modifier | modifier le code]
Article connexe[modifier | modifier le code]
Lien externe[modifier | modifier le code]
Références[modifier | modifier le code]
- Andries E. Brouwer, Arieh M. Cohen et Arnold Neumaier, « Graphs Related to Codes: The Truncated Witt Graph Associated to M23 », dans Distance-Regular Graphs, New York, Springer-Verlag, coll. « Ergebnisse der Mathematik und ihrer Grenzgebiete » (no 18), , xvii+495 p. (ISBN 978-3-642-74343-6, DOI 10.1007/978-3-642-74341-2), §11.4.B, p. 367-368.
- E. R. van Dam et W. H. Haemers, « Which Graphs Are Determined by Their Spectrum? », Linear Algebra and Its Applications, vol. 373, , p. 139-162 (DOI 10.1016/S0024-3795(03)00483-X).
