Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Graphe distance-transitif
Résumé
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. 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.
Tout graphe distance-transitif est distance-régulier. La réciproque est fausse et le plus petit graphe distance-régulier mais pas distance-transitif est le graphe de Shrikhande.
Tout graphe distance-transitif est symétrique.
Les graphes complets, les graphes bipartis complets, les hypercubes sont distance-transitifs.
Il existe exactement 12 graphes cubiques distance-transitifs : le graphe tétraédrique, le graphe biparti complet K, le graphe hexaédrique, le graphe de Petersen, le graphe de Heawood, le graphe de Pappus, le graphe de Desargues, le graphe dodécaédrique, le graphe de Coxeter, le graphe de Tutte–Coxeter, le graphe de Foster et le graphe de Biggs-Smith.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.