title: Graphe semi-symétrique
text: # Graphe semi-symétrique
  
  Familles de graphes définies par leurs automorphismes :
  
  | distance-transitif | → | distance-régulier | ← | fortement régulier |
  | - | - | - | - | - |
  | symétrique (arc-transitif) | ← | t-transitif, (t ≥ 2) | | symétrique gauche (en) |
  | $_{(siconnexe)}$ sommet-transitif et arête-transitif | → | régulier et arête-transitif | → | arête-transitif |
  | sommet-transitif | → | régulier | → | $_{(sibiparti)}$ birégulier |
  | graphe de Cayley | ← | zéro-symétrique | | asymé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.
  
  ## 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^2,$ 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.
  
  * Graphe de Folkman, plus petit graphe semi-symétrique, à 20 sommets.
  * Graphe de Gray, plus petit graphe cubique semi-symétrique, à 54 sommets.
  * Graphe de Ljubljana, graphe cubique semi-symétrique à 112 sommets.
  * 12-cage de Tutte, graphe cubique semi-symétrique à 126 sommets.
  