Graphe symétrique

En théorie des graphes, un graphe non orienté G=(V,E) est symétrique (ou arc-transitif) si, étant donné deux paires quelconques de sommets reliés par une arête u₁—v₁ et u₂—v₂ de G, il existe un automorphisme de graphe :

${\displaystyle f:V\rightarrow V}$

Le Graphe de Petersen est un graphe cubique symétrique.

tel que

${\displaystyle f(u_{1})=u_{2}}$ et ${\displaystyle f(v_{1})=v_{2}}$[1].

En d'autres termes, un graphe est symétrique si son groupe d'automorphismes agit transitivement sur ses paires ordonnées de sommets reliés[2]. Un tel graphe est parfois appelé 1-arc-transitif[2].

Par définition, un graphe symétrique sans sommet isolé est sommet-transitif[1] et arête-transitif. La distinction entre arête-transitif et arc-transitif est subtile[3]: « Arête-transitif » signifie que pour toute paire d'arêtes ${\displaystyle u_{1}{-}u_{2}}$ et ${\displaystyle v_{1}{-}v_{2}}$, il existe un automorphisme ${\displaystyle f}$ qui envoie l'une sur l'autre, donc tel que ${\displaystyle f(u_{1}){-}f(u_{2})=v_{1}{-}v_{2}}$, alors que « arc-transitif » demande qu'en plus ${\displaystyle f(u_{1})=v_{1},f(u_{2})=v_{2}}$ et que, pour un autre automorphisme ${\displaystyle f'}$, on ait ${\displaystyle f'(u_{1})=v_{2},f'(u_{2})=v_{1}}$. Si un graphe est arête-transitif sans être 1-transitif, alors toute arête peut être envoyée sur toute autre, mais seulement d'une seule parmi les deux façons possibles.

Le terme « symétrique » est d'ailleurs parfois employé pour désigner un graphe qui soit simplement arête-transitif et sommet-transitif ; cette utilisation du terme est ambiguë, car il existe des graphes qui sont arête-transitifs et sommet-transitifs sans être arc-transitifs[4]. Ces graphes sont rares : le plus petit exemple est le graphe de Doyle[5].

Dans les cas des graphes de degré impair, un graphe arête-transitif et sommet-transitif est cependant nécessairement arc-transitif[6].