Graphe arête-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[modifier | modifier le code]
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[1],[2]. 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[modifier | modifier le code]
Tout graphe biparti complet est arête-transitif[1].
Si un graphe connexe est arête-transitif mais pas sommet-transitif, il est biparti[1].
Un graphe connexe est arête-transitif si et seulement si son line graph est sommet-transitif[2].
Exemples[modifier | modifier le code]
Le graphe de Gray est semi-symétrique, c'est-à-dire arête-transitif et régulier mais pas sommet-transitif[3].
Notes et références[modifier | modifier le code]
- (en) Norman Biggs, Algebraic Graph Theory, 2d Edition, Cambridge University Press, , 214 p. (ISBN 978-0-521-45897-9, lire en ligne), p. 115-116
- (en) Eric W. Weisstein, « Edge-Transitive Graph », sur mathworld.wolfram.com (consulté le )
- (en) Dragan Marušič, Tomaž Pisanski et Steve Wilson, « The genus of the GRAY graph is 7 », European Journal of Combinatorics, topological Graph Theory and Graph Minors, second issue, vol. 26, no 3, , p. 377–385 (ISSN 0195-6698, DOI 10.1016/j.ejc.2004.01.015, lire en ligne, consulté le )
