Graphe arête-transitif

Familles de graphes définies par leurs automorphismes
distance-transitif	→	distance-régulier	←	fortement régulier
↓
symétrique (arc-transitif)	←	t-transitif, $(t \geq 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 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

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

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

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

↑ ^{a b et c} (en) Norman Biggs, Algebraic Graph Theory, 2^d Edition, Cambridge University Press, 1993, 214 p. (ISBN 978-0-521-45897-9, lire en ligne), p. 115-116
↑ ^{a et b} (en) Eric W. Weisstein, « Edge-Transitive Graph », sur mathworld.wolfram.com (consulté le 9 mars 2019)
↑ (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, n^o 3,‎ 1^er avril 2005, p. 377–385 (ISSN 0195-6698, DOI 10.1016/j.ejc.2004.01.015, lire en ligne, consulté le 2 juillet 2019)

Portail des mathématiques

[:0-1] {a b et c} (en) Norman Biggs, Algebraic Graph Theory, 2^d Edition, Cambridge University Press, 1993, 214 p. (ISBN 978-0-521-45897-9, lire en ligne), p. 115-116

[:1-2] {a et b} (en) Eric W. Weisstein, « Edge-Transitive Graph », sur mathworld.wolfram.com (consulté le 9 mars 2019)

[3] (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, n^o 3,‎ 1^er avril 2005, p. 377–385 (ISSN 0195-6698, DOI 10.1016/j.ejc.2004.01.015, lire en ligne, consulté le 2 juillet 2019)

[1]

[2]

[3]