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
Image illustrative de l’article 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

Propriétés

modifier

Propriétés générales

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

Coloration

modifier

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.

Propriétés algébriques

modifier

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.

Chemins et cycles hamiltoniens

modifier

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

Galerie

modifier

Notes et références

modifier
  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 homepage
  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.