vignette|Graphe de Gray, arête-transitif et régulier mais pas sommet-transitif. En théorie des graphes, un graphe non-orienté est arête-transitif si pour tout couple d'arêtes, il existe un automorphisme de graphe envoyant la première arête sur la seconde.
Définitions Un graphe non-orienté est arête-transitif si pour tout couple d'arêtes, il existe un automorphisme de graphe envoyant la première arête sur la seconde. En d'autres termes, un graphe est arête-transitif si son groupe d'automorphismes agit transitivement sur l'ensemble de ses arêtes.
De manière informelle, cette propriété signifie que toutes les arêtes jouent le même rôle dans le graphe.
Propriétés Tout graphe biparti complet est arête-transitif.
Si un graphe connexe est arête-transitif mais pas sommet-transitif, il est biparti.
Un graphe connexe est arête-transitif si et seulement si son line graph est sommet-transitif.
Exemples Le graphe de Gray est semi-symétrique, c'est-à-dire arête-transitif et régulier mais pas sommet-transitif.
Notes et références
Catégorie:Famille de graphes