Graphe semi-symétrique

En théorie des graphes, un graphe non-orienté est semi-symétrique s'il est arête-transitif et régulier, mais pas sommet-transitif. Autrement dit, un graphe est semi-symétrique s'il est régulier et si son groupe d'automorphismes agit transitivement sur ses arêtes, mais pas sur ses sommets. Tout graphe semi-symétrique est biparti, et son groupe d'automorphisme agit transitivement sur les deux sous-ensembles de sommets de la bipartition. Il n'existe aucun graphe semi-symétrique d'ordre 2p ou 2p, où p est un nombre premier. Le plus petit graphe semi-symétrique est le graphe de Folkman, qui possède 20 sommets. Tous les graphes cubiques semi-symétriques d'ordre inférieur à 768 sont connus. Le plus petit d'entre eux est le graphe de Gray, qui possède 54 sommets. Fichier:Folkman graph alt.svg|[[Graphe de Folkman]], plus petit graphe semi-symétrique, à 20 sommets. Fichier:Gray graph hamiltonian.svg|[[Graphe de Gray]], plus petit graphe cubique semi-symétrique, à 54 sommets. Fichier:Ljubljana graph hamiltonian.svg|[[Graphe de Ljubljana]], graphe cubique semi-symétrique à 112 sommets. Fichier:Tutte 12-cage.svg|[[12-cage de Tutte]], graphe cubique semi-symétrique à 126 sommets.