Graphe distance-transitif
From Wikipedia, the free encyclopedia
En théorie des graphes, un graphe non-orienté est distance-transitif si pour tous sommets u, v, x, y tels que u et v d'une part et x et y d'autre part sont à même distance, il existe un automorphisme de graphe envoyant u sur x et v sur y[1]. Autrement dit, un graphe est distance-transitif si son groupe d'automorphisme agit transitivement sur chacun des ensembles de paires de sommets à même distance[2].
Tout graphe distance-transitif est distance-régulier[3]. La réciproque est fausse et le plus petit graphe distance-régulier mais pas distance-transitif est le graphe de Shrikhande[2].
Tout graphe distance-transitif est symétrique.
