Graphe demi-transitif

théorie des graphes
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

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].

Propriétés

modifier

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

modifier
 
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].

Notes et références

modifier
  1. a et b (en) Ming-Yao Xu, « Half-Transitive Graphs of Prime-Cube Order », Journal of Algebraic Combinatorics, vol. 1, no 3,‎ , p. 275–282 (ISSN 1572-9192, DOI 10.1023/A:1022440002282, lire en ligne, consulté le )
  2. (en) D Marušič et R Nedela, « Maps and Half-transitive Graphs of Valency 4 », European Journal of Combinatorics, vol. 19, no 3,‎ , p. 345–354 (ISSN 0195-6698, DOI 10.1006/eujc.1998.0187, lire en ligne, consulté le )
  3. (en) I. Z. Bouwer, « Vertex and Edge Transitive, but not 1-Transitive, Graphs », Canadian Mathematical Bulletin, vol. 13, no 2,‎ , p. 231–237 (ISSN 0008-4395 et 1496-4287, DOI 10.4153/CMB-1970-047-8, lire en ligne, consulté le )