Graphe de Coxeter
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  |
|
Propriétés
modifierPropriétés générales
modifierLe 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].
Coloration
modifierLe 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.
Propriétés algébriques
modifierLe 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.
Chemins et cycles hamiltoniens
modifierLe 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].
Galerie
modifier-
Le graphe obtenu depuis le graphe de Coxeter par excision d'une arête -
Le graphe de Coxeter admet une 3-coloration -
Le graphe de Coxeter peut être dessiné sur le plan avec 11 croisements d'arêtes
Notes et références
modifier- (en) Brouwer, A. E. Coxeter Graph
- (en) H.S.M. Coxeter, My graph, Proc. London Math. Soc. 46 (1983) 117-136.
- (en) Gordon Royle F028A
- (en) Rectilinear Drawings of Famous Graphs on Geoffrey Exoo homepage
- (en) Pegg, E. T. and Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 2009
- (en) Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002
- (en) Royle, G. "Cubic Symmetric Graphs (The Foster Census)."
- (en) Bondy, J. A. "Variations of the Hamiltonian Theme." Canad. Math. Bull. 15, 57-62, 1972.
