Semisymetrický graf je neorientovaný okrajově tranzitivní pravidelný graf , který není vertexově tranzitivní . Jinými slovy, graf je semisymetrický, pokud má každý vrchol stejný počet dopadajících hran a pro každý pár hran existuje symetrie, která mapuje jednu hranu na druhou, ale existuje pár vrcholů, pro které symetrie neexistuje. který mapuje jeden vrchol na druhý.
Polosymetrický graf musí být bipartitní a jeho skupina automorfismu musí působit tranzitivně na každé ze dvou vrcholových částí bipartitního grafu. Například ve Folkmanově grafu zobrazeném v diagramu nelze zelené vrcholy mapovat na červenou žádným automorfismem, ale jakékoli dva vrcholy stejné barvy jsou vůči sobě symetrické.
Semisymetrické grafy byly poprvé studovány Dauberem, studentem Franka Harariho , v nyní nedostupném článku s názvem „On line-ale not point-symmetric grafs“. Papír viděl John Folkman, jehož práce, publikovaná v roce 1967, obsahovala nejmenší semisymetrický graf, nyní známý jako Folkmanův graf , s 20 vrcholy [1] . Termín „semisymetrický“ poprvé použili Klin, Lauri a Ziv-Av v článku, který publikovali v roce 1978 [2] .
Nejmenším kubickým semisymetrickým grafem (tj. grafem, ve kterém každý vrchol dopadá přesně na tři hrany) je Grayův graf s 54 vrcholy . Bower [3] jako první objevil, že graf je semisymetrický . To, že je graf nejmenší mezi kubickými semisymetrickými grafy, dokázali Marusic a Malnich [4] .
Jsou známy všechny kubické semisymetrické grafy až do 768 vrcholů. Podle Kondera, Malnic, Marusiče a Potochnika jsou čtyři nejmenší kubické semisymetrické grafy po Grayově grafu 110-vertexový graf Ivanov-Iofinova , 112-vertexový graf Lublaně [5] , 120-vertexový graf s obvodem 8, a 12-buněčná Tatta [6] .