En théorie des graphes, un graphe non-orienté est demi-transitif s'il est sommet-transitif et arête-transitif, mais pas symétrique. Autrement dit, un graphe est demi-transitif si son groupe d'automorphismes agit transitivement sur ses sommets et ses arêtes, mais pas sur ses arcs c'est-à-dire ses paires ordonnées de sommets adjacents.
Propriétés Un graphe sommet-transitif et arête-transitif de degré impair est arc-transitif. Il n'existe donc pas de graphe demi-transitif de degré impair.
En revanche un graphe 2k-régulier demi-transitif peut être construit pour tout k⩾2.
Exemples gauche|vignette|Le graphe de Doyle est le plus petit graphe demi-transitif. Le plus petit graphe demi-transitif est le graphe de Holt (ou graphe de Doyle), un graphe 4-régulier à 27 sommets et 54 arêtes.
Notes et références
Catégorie:Famille de graphes