Un graf semisimetric este un graf regulat nedirecționat tranzitiv la muchie care nu este tranzitiv la vârf . Cu alte cuvinte, un grafic este semisimetric dacă fiecare vârf are același număr de muchii incidente și pentru fiecare pereche de muchii există o simetrie care mapează o muchie la alta, dar există o pereche de vârfuri pentru care nu există simetrie. care mapează un vârf la altul.
Un graf semisimetric trebuie să fie bipartit , iar grupul său de automorfism trebuie să acționeze tranzitiv pe fiecare dintre cele două părți de vârf ale grafului bipartit. De exemplu, în graficul Folkman prezentat în diagramă, vârfurile verzi nu pot fi mapate la roșu prin niciun automorfism, dar oricare două vârfuri de aceeași culoare sunt simetrice unul față de celălalt.
Graficele semisimetrice au fost studiate pentru prima dată de Dauber, un student al lui Frank Harari , într-o lucrare acum indisponibilă intitulată „Grafe pe linie, dar nu cu simetrie punctuală”. Lucrarea a fost văzută de John Folkman, a cărui lucrare, publicată în 1967, includea cel mai mic grafic semisimetric, cunoscut acum sub numele de Folkman Graph , cu 20 de vârfuri [1] . Termenul „semisimetric” a fost folosit pentru prima dată de Klin, Lauri și Ziv-Av într-o lucrare publicată de ei în 1978 [2] .
Cel mai mic grafic cubic semisimetric (adică un grafic în care fiecare vârf este incident cu exact trei muchii) este graficul Gray cu 54 de vârfuri . Bower [3] a fost primul care a descoperit că un grafic este semisimetric . Faptul că graficul este cel mai mic dintre graficele cubice semisimetrice a fost demonstrat de Marusic și Malnich [4] .
Sunt cunoscute toate graficele cubice semisimetrice de până la 768 de vârfuri. Conform lui Konder, Malnic, Marusic și Potochnik, cele mai mici patru grafice cubice semisimetrice după graficul Gray sunt graficul Ivanov-Iofinova cu 110 vârfuri , graficul Ljubljana cu 112 vârfuri [5] , graficul cu 120 de vârfuri cu circumferința 8, și Tatta cu 12 celule [6] .