Graf przechodni krawędzi

W matematycznej dziedzinie teorii grafów graf przechodni krawędziowo jest grafem $G$ takim, że przy danych dowolnych dwóch krawędziach $e 1$ i $e 2$ z $G$ istnieje automorfizm G , który odwzorowuje $e 1$ na $e 2$ $.$

Innymi słowy, graf jest przechodni krawędziowo, jeśli jego grupa automorfizmów działa przechodnio na jego krawędziach.

Przykłady i właściwości

Graf Graya jest przechodni przez krawędzie i regularny , ale nie przechodni przez wierzchołki .

Liczba połączonych prostych grafów przechodnich krawędzi na n wierzchołkach wynosi 1, 1, 2, 3, 4, 6, 5, 8, 9, 13, 7, 19, 10, 16, 25, 26, 12, 28 .. (sekwencja A095424 w OEIS )

Grafy przechodnie krawędziowe obejmują wszystkie grafy symetryczne , takie jak wierzchołki i krawędzie sześcianu . Grafy symetryczne są również przechodnie przez wierzchołki (jeśli są połączone ), ale generalnie grafy przechodnie krawędziowe nie muszą być przechodnie przez wierzchołki. Każdy połączony graf przechodni krawędzi, który nie jest przechodni wierzchołków, musi być dwudzielny (a zatem może być pokolorowany tylko dwoma kolorami) oraz półsymetryczny lub dwuregularny .

Przykłady grafów przechodnich krawędzi, ale nie wierzchołków, obejmują pełne grafy dwudzielne, $}} }$ $K_$ { . Dla grafów na n wierzchołkach istnieje (n-1)/2 takich grafów dla nieparzystego n i (n-2) dla parzystego n. Dodatkowe grafy przechodnie krawędzi, które nie są symetryczne, można w niektórych przypadkach utworzyć jako podgrafy tych kompletnych grafów dwudzielnych. Podgrafy kompletnych grafów dwudzielnych K _m,n istnieją, gdy m i n mają wspólny czynnik większy niż 2. Gdy największy wspólny czynnik wynosi 2, podgrafy istnieją, gdy 2n/m jest parzyste lub gdy m=4 i n jest nieparzystą wielokrotnością 6 Zatem podgrafy przechodnie krawędziowe istnieją dla K _3,6 , K _4,6 i K _5,10 , ale nie dla K _4,10 . Alternatywną konstrukcją niektórych grafów przechodnich krawędzi jest dodanie wierzchołków do punktów środkowych krawędzi grafu symetrycznego z v wierzchołkami i e krawędziami, tworząc graf dwudzielny z e wierzchołkami rzędu 2 i v rzędu 2e/v.

Graf przechodni krawędziowy, który jest również regularny , ale nadal nie jest przechodni względem wierzchołków, nazywany jest półsymetrycznym . Graf Graya , graf sześcienny o 54 wierzchołkach, jest przykładem grafu regularnego, który jest przechodni przez krawędź, ale nie przechodni przez wierzchołki. Graf Folkmana , graf kwartalny o 20 wierzchołkach, jest najmniejszym takim grafem.

Łączność wierzchołków grafu przechodniego krawędzi zawsze jest równa jego minimalnemu stopniowi .

Zobacz też

Krawędź przechodnia (w geometrii)

Linki zewnętrzne

Weisstein, Eric W. „Graf przechodni krawędzi” . MathWorld .

Rodziny grafów zdefiniowane przez ich automorfizmy
przechodnie na odległość	→	odległość regularna	←	mocno regularny
↓
symetryczny (przechodni łuku)	←	t -przechodnia, $t \geq 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