Rodziny grafów określone przez ich automorfizmy | ||||
---|---|---|---|---|
odległość-przechodnia | → | regularne odległości | ← | mocno regularne |
↓ | ||||
symetryczny (przechodni łuku) | ← | t - przechodnie, ( t ≥ 2) | symetryczny lewy ( cal ) | |
↓ | ||||
(jeśli są połączone) przechodnie przez wierzchołki i przechodnie od krawędzi |
→ | regularne i przechodnie krawędziowe | → | przechodnia krawędziowa |
↓ | ↓ | ↓ | ||
przechodni w górę | → | regularny | → |
(jeśli dwustronne) dwurzędowe |
↑ | ||||
Wykres Cayleya | ← | zero-symetryczny | asymetryczny |
W teorii wykres , A niezorientowane wykres to dystansu przechodni , jeżeli dla wszystkich wierzchołków u, v, x, y, tak że U i V z jednej strony, a X i Y, z drugiej strony, znajdują się w tej samej odległości , istnieje wykres automorfizmu wysyłający u przez x i v przez y. Innymi słowy, graf jest przechodni na odległość, jeśli jego grupa automorfizmu działa przejściowo na każdy ze zbiorów par wierzchołków w tej samej odległości.
Każdy wykres przechodni z odległością jest zależny od odległości . Odwrotność jest fałszem, a najmniejszym wykresem odległościowo-regularnym, ale nie przechodnim względem odległości, jest wykres Shrikhande'a .
Każdy wykres przechodni na odległość jest symetryczny .
W graf pełny , to kompletne graf dwudzielny , tym hipersześcian są na odległość przechodnia.
Istnieje dokładnie 12 wykresy sześciennych na odległość przechodni: the czworościenne wykres The zakończeniu dwustronnego wykres K 3,3 The sześciokątne wykres The wykres Petersen The wykres Heawood The wykres Pappus , że Desargues wykres The dodecahedral wykres The wykres Coxeter The Tutte - Coxeter wykres The Foster wykres a wykres Biggs-Smith .