Graphe de Coxeter

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

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].

Propriétés

Propriétés générales

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].

Coloriage

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 tels que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes. Ce nombre est minimal.

Propriétés algébriques

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'automorphisme le groupe projectif linéaire PGL(2,7) d'ordre 336.

Le polynôme caractéristique du graphe de Coxeter est : (x − 3)(x − 2)⁸(x + 1)⁷(x² + 2x − 1)⁶. 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

Le graphe de Coxeter est remarquable car il est à la fois sommet-transitif et non-hamiltonien. C'est, avec K₂ 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

• 

  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

1. ↑ (en) Brouwer, A. E. Coxeter Graph
2. ↑ (en) H.S.M. Coxeter, My graph, Proc. London Math. Soc. 46 (1983) 117-136.
3. ↑ (en) Gordon Royle F028A
4. ↑ (en) Rectilinear Drawings of Famous Graphs on Geoffrey Exoo hompage
5. ↑ (en) Pegg, E. T. and Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 2009
6. ↑ (en) Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002
7. ↑ (en) Royle, G. "Cubic Symmetric Graphs (The Foster Census)."
8. ↑ (en) Bondy, J. A. "Variations of the Hamiltonian Theme." Canad. Math. Bull. 15, 57-62, 1972.