Wykres półsymetryczny - Semi-symmetric graph
W matematycznej dziedzinie teorii grafów , o pół-symetryczny wykres jest nieukierunkowane wykres czyli krawędzi przechodnia i regularne , ale nie vertex-przechodnia . Innymi słowy, graf jest półsymetryczny, jeśli każdy wierzchołek ma taką samą liczbę krawędzi padających i istnieje symetria przenosząca dowolne krawędzie grafu do dowolnej innej krawędzi, ale istnieje pewna para wierzchołków tak, że nie ma symetrii odwzorowuje pierwszy na drugi.
Nieruchomości
Półsymetryczny graf musi być dwudzielny , a jego grupa automorfizmu musi działać przechodnie na każdym z dwóch zbiorów wierzchołków dwudzielności (w rzeczywistości regularność nie jest wymagana do zachowania tej własności). Na przykład na przedstawionym tu diagramie grafu Folkmana , zielone wierzchołki nie mogą być odwzorowane na czerwone przez żaden automorfizm, ale każde dwa wierzchołki tego samego koloru są symetryczne względem siebie.
Historia
Wykresy półsymetryczne po raz pierwszy badał E. Dauber, uczeń F. Harary'ego, w niedostępnej już pracy pt. Było to widoczne przez Jon Folkman , którego papier, opublikowane w 1967 roku, zawiera najmniejszą pół-symetryczny wykres, obecnie znany jako Folkman wykresie , 20 wierzchołków. Termin „półsymetryczny” został po raz pierwszy użyty przez Klin et al. w gazecie, którą opublikowali w 1978 roku.
Wykresy sześcienne
Najmniejszy sześcienny półsymetryczny wykres (to znaczy taki, w którym każdy wierzchołek pada na dokładnie trzy krawędzie) to wykres Graya na 54 wierzchołkach. Po raz pierwszy został zaobserwowany jako półsymetryczny przez Bouwera (1968) . Dragan Marušič i Aleksander Malnič udowodnili, że jest to najmniejszy sześcienny półsymetryczny wykres.
Znane są wszystkie sześcienne półsymetryczne wykresy do 768 wierzchołków. Według Condera , Malniča, Marušiča i Potočnika, cztery najmniejsze możliwe sześcienne półsymetryczne wykresy po wykresie Graya to wykres Iofinova-Ivanov na 110 wierzchołkach, wykres Lublana na 112 wierzchołkach, wykres na 120 wierzchołkach o obwodzie 8 i Tutte 12-klatkowe .