Graphe semi-symétrique
# 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.
