Graphe demi-transitif

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^[1].

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)
↓
(si connexe) sommet-transitif et arête-transitif	→	régulier et arête-transitif	→	arête-transitif
↓		↓		↓
sommet-transitif	→	régulier	→	(si biparti) birégulier
↑
graphe de Cayley	←	zéro-symétrique		asymétrique

Propriétés

Un graphe sommet-transitif et arête-transitif de degré impair est arc-transitif^[2]. 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^[3].

Exemples

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^[1].