Chapitre 10 Un petit catalogue

Ce chapitre contient quelques graphes de Cayley non-orientés, connexes de petits ordres et degrés. On n'ira sûrement pas jusqu'à 1003.

Certains des graphes se trouvent déjà dans [134], un ouvrage recommandé à qui aime voir les graphes.

Pour le degré 2 on trouve les cycles, et c'est tout.

Pour le degré 3, on a 3 élément d'ordre 2 ou un élément d'ordre 2 et un autre élément. Dans la cas commutatif, on a les prismes (par

_n×

₂,{±(1,0),(0,1)}), et les échelles de Moebius (par

_2n,{±1,n/2}) de la figure 10.1. Ce ne sont pas les seules façons d'obtenir ces graphes.

Figure 10.1 : Prismes et échelles de Moebius

Les autres graphes de Cayley à 12 sommets de degré 3

Figure 10.2 : Autres graphes à 12 sommets

À l'ordre 14, il y a aussi le graphe de Heawood.

Figure 10.3 : Le graphe de Heawood

10.1 Les graphes planaires

Outre ceux déjà vus (figures 10.1 et 10.2), et la famille des antiprismes (par

_2n,{±1,±2}, figure 10.4), les graphes de Cayley planaires sont les 5 associés aux polyèdres réguliers, ceux obtenus en les tronquant, et les versions snub (camus), à part deux exceptions: ce serait trop simple!

Figure 10.4 : Un antiprisme

Voici la série à partir du tétraèdre : tétraèdre, tétraèdre tronqué, octaèdre, icosaèdre.

Figure 10.5 : À partir du tétraèdre

Voici la série obtenue à partir du cube : cube, cube tronqué, cuboctaèdre, snub-cube (figure 10.6).

Figure 10.6 : À partir du cube

Figure 10.7 : Octaèdre tronqué

Figure 10.8 : Icosaèdre tronqué: ballon de foute

Figure 10.9 : À partir du dodécaèdre

Ajoutons les deux graphes de Cayley suivants, qui proviennent du cube et du dodécaèdre. Le tétraèdre trituré de la même façon donnerait le cuboctaèdre (figure 10.10).

Figure 10.10 : Graphes avec 3 sortes de faces

Un petit détour par les graphes planaires infinis, qui correspondent à un pavage périodique du plan, car en passant au quotient par un réseau de translations, on obtient un graphe de Cayley dessinable sur le tore (figure 10.11).

Figure 10.11 : Pavages de Cayley du plan

Un dernier point: l'avantage des graphes planaires est que les cycles de longueur >2 se voient avec les faces. Cela permet de trouver assez vite un système de relations.

Exercice bien long: trouver les intrus (qui ne sont pas des graphes de Cayley) et une façon (au moins) de représenter les autres à partir d'un groupe et d'un génerateur.