Graphe sommet-transitif

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Familles de graphes définies par leurs automorphismes
distance-transitif distance-régulier fortement régulier
symétrique (transitif aux arcs) t-transitif, (t ≥ 2) symétrique gauche
(si connexe)
sommet-transitif et arc-transitif
régulier et arc-transitif arc-transitif
sommet-transitif régulier (si bipartite)
birégulier
graphe de Cayley zéro-symétrique asymétrique

En théorie des graphes, un graphe non-orienté est sommet-transitif si pour tout couple de sommets, il existe un automorphisme de graphe qui envoie le premier sommet sur le deuxième. De manière informelle cette propriété indique que tous les sommets jouent exactement le même rôle à l'intérieur du graphe.

Définitions[modifier | modifier le code]

Un graphe est sommet-transitif si pour tout couple de sommets, il existe un automorphisme de graphe qui envoie le premier sommet sur le deuxième[1]. En d'autres termes, un graphe est sommet-transitif si son groupe d'automorphismes agit transitivement sur l'ensemble de ses sommets.

Propriétés[modifier | modifier le code]

Un graphe sommet-transitif est régulier[1], mais la réciproque n'est pas nécessairement vraie[2].

Exemples[modifier | modifier le code]

Les graphes complets sont sommet-transitifs. Les graphes symétriques sans sommets isolés et les graphes de Cayley, sont sommet-transitifs.

Notes et références[modifier | modifier le code]

  1. a et b Olivier Fouquet, Théorie des graphes : une brève introduction (avec un biais algébrique assumé), (lire en ligne)
  2. (en) Eric W. Weisstein, « Vertex-Transitive Graph », MathWorld.