Graf półprzechodni

Rodziny grafów zdefiniowane przez ich automorfizmy
przechodnie na odległość	→	odległość regularna	←	mocno regularny
↓
symetryczny (przechodni łuku)	←	t -przechodnia, t ≥ 2		skośno-symetryczny
↓
(jeśli jest połączony) wierzchołki i krawędzie przechodnie	→	przechodnie krawędziowe i regularne	→	przechodnie krawędziowe
↓		↓		↓
przechodnie wierzchołków	→	regularny	→	(jeśli dwustronny) dwuregularny
↑
Wykres Cayleya	←	zero-symetryczny		asymetryczny

W matematycznej dziedzinie teorii grafów graf półprzechodni to graf , który jest zarówno przechodni wierzchołków, jak i przechodni krawędzi , ale nie jest symetryczny . Innymi słowy, graf jest półprzechodni, jeśli jego grupa automorfizmów działa przechodnio zarówno na jego wierzchołki, jak i krawędzie, ale nie na uporządkowane pary połączonych wierzchołków.

Graf Holta jest najmniejszym grafem półprzechodnim. Brak symetrii odbicia na tym rysunku podkreśla fakt, że krawędzie nie są równoważne ich odwrotności.

Każdy spójny graf symetryczny musi być wierzchołkowo-przechodni i krawędziowo-przechodni , a odwrotność jest prawdziwa dla grafów nieparzystego stopnia, tak że grafy półprzechodnie nieparzystego stopnia nie istnieją. Istnieją jednak grafy półprzechodnie o parzystym stopniu. Najmniejszym grafem półprzechodnim jest graf Holta o 4 stopniu i 27 wierzchołkach.