Wykres półsymetryczny
W matematycznej dziedzinie teorii grafów graf półsymetryczny to graf nieskierowany , który jest przechodni krawędziowo i regularny , ale nie jest przechodni względem wierzchołków . Innymi słowy, graf jest półsymetryczny, jeśli każdy wierzchołek ma taką samą liczbę incydentnych krawędzi i istnieje symetria łącząca dowolną krawędź grafu z dowolną inną jego krawędzią, ale istnieje taka para wierzchołków, że żadna symetria odwzorowuje pierwszy na drugi.
Nieruchomości
Graf półsymetryczny musi być dwudzielny , a jego grupa automorfizmów musi działać przechodnie na każdym z dwóch zestawów wierzchołków podziału dwudzielnego (w rzeczywistości regularność nie jest wymagana, aby ta właściwość była zachowana). Na przykład na pokazanym tutaj diagramie wykresu Folkmana zielonych wierzchołków nie można odwzorować na czerwone za pomocą żadnego automorfizmu, ale każde dwa wierzchołki tego samego koloru są względem siebie symetryczne.
Historia
Grafy półsymetryczne zostały po raz pierwszy zbadane przez E. Daubera, ucznia F. Harary'ego, w artykule, który nie jest już dostępny, zatytułowanym „On line- but not point-symmetric graphs”. Zauważył to Jon Folkman , którego artykuł opublikowany w 1967 roku zawiera najmniejszy graf półsymetryczny, obecnie znany jako graf Folkmana , na 20 wierzchołkach. Termin „półsymetryczny” został po raz pierwszy użyty przez Klina i in. w artykule, który opublikowali w 1978 roku.
Wykresy sześcienne
Najmniejszym grafem sześciennym półsymetrycznym (to znaczy takim, w którym każdy wierzchołek pokrywa się z dokładnie trzema krawędziami) jest graf Graya na 54 wierzchołkach. Po raz pierwszy zaobserwowano, że jest półsymetryczny przez Bouwera (1968) . Dragan Marušič i Aleksander Malnič udowodnili, że jest to najmniejszy sześcienny graf półsymetryczny .
Znane są wszystkie sześcienne grafy półsymetryczne na maksymalnie 10000 wierzchołkach. Według Condera , Malniča, Marušiča i Potočnika, cztery najmniejsze możliwe sześcienne grafy półsymetryczne po grafie Graya to graf Iofinova – Ivanov na 110 wierzchołkach, graf Ljubljana na 112 wierzchołkach, graf na 120 wierzchołkach o obwodzie 8 i Tutte 12-klatka .