Graphe de Coxeter
De Wikipédia, l'encyclopédie libre
De Wikipédia, l'encyclopédie libre
En théorie des graphes, le graphe de Coxeter est un graphe cubique symétrique à 28 sommets et 42 arêtes[1]. Il est nommé en l'honneur de H.S.M. Coxeter qui l'appelait « My graph[2] ».
| Graphe de Coxeter | |
 Représentation du graphe de Coxeter. | |
| Nombre de sommets | 28 |
|---|---|
| Nombre d'arêtes | 42 |
| Distribution des degrés | 3-régulier |
| Rayon | 4 |
| Diamètre | 4 |
| Maille | 7 |
| Automorphismes | 336 (PGL(2,7)) |
| Nombre chromatique | 3 |
| Indice chromatique | 3 |
| Propriétés | Hypohamiltonien Cubique Symétrique |
| modifier | |
Le diamètre du graphe de Coxeter, l'excentricité maximale de ses sommets, est 4, son rayon, l'excentricité minimale de ses sommets, est 4 et sa maille, la longueur de son plus court cycle, est 7[3]. Il s'agit d'un graphe 3-sommet-connexe et d'un graphe 3-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 3 sommets ou de 3 arêtes.
Le graphe de Coxeter n'est pas planaire. En fait pour le dessiner sur un plan il faut nécessairement que plusieurs arêtes se croisent. Il est possible de le dessiner avec seulement 11 croisements, mais le fait que ce nombre soit minimal est une conjecture[4]. Une autre conjecture énoncée par Pegg et Exoo en 2009 expose que le graphe de Coxeter, avec ses 28 sommets, serait le plus petit graphe cubique nécessitant 11 croisements pour être dessiné sur le plan[5].
Le nombre chromatique du graphe de Coxeter est 3. C'est-à-dire qu'il est possible de le colorer avec 3 couleurs de telle façon que deux sommets reliés par une arête soient toujours de couleurs différentes. Ce nombre est minimal.
L'indice chromatique du graphe de Coxeter est 3. Il existe donc une 3-coloration des arêtes du graphe telle que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes. Ce nombre est minimal.
Le graphe de Coxeter est symétrique, c'est-à-dire que son groupe d'automorphismes agit transitivement sur ses arêtes, ses sommets et ses arcs. Il est donc également arête-transitif et sommet-transitif. Le graphe de Coxeter est l'unique graphe cubique symétrique à 28 sommets et sa notation dans le Foster Census, le catalogue classifiant tous les graphes cubiques symétriques, est F28A[6],[7].
Il a pour groupe d'automorphismes le groupe projectif linéaire PGL(2,7) d'ordre 336.
Le polynôme caractéristique de la matrice d'adjacence du graphe de Coxeter est : . Le graphe de Coxeter est déterminé de façon unique par son spectre de graphe, l'ensemble des valeurs propres de sa matrice d'adjacence.
Le graphe de Coxeter est remarquable car il est à la fois sommet-transitif et non-hamiltonien. C'est, avec et le graphe de Petersen, un des cinq graphes sommet-transitif connexe sans cycle hamiltonien connu. La conjecture de Lovász stipule que tous les graphes sommet-transitifs sont hamiltoniens sauf ces cinq là.
Bien que le graphe de Coxeter ne possède pas de cycle hamiltonien, il possède un chemin hamiltonien. J. A. Bondy prouva en 1972 qu'il est hypohamiltonien, c'est-à-dire que la suppression de n'importe quel sommet du graphe de Coxeter suffit à le rendre hamiltonien[8].
Seamless Wikipedia browsing. On steroids.
