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.
Propriétés 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.
Exemples 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.
Notes et références
Catégorie:Famille de graphes