A félszimmetrikus gráf egy irányítatlan éltranzitív reguláris gráf , amely nem csúcstranzitív . Más szóval, egy gráf félszimmetrikus, ha minden csúcsnak ugyanannyi beeső éle van, és minden élpárhoz létezik egy szimmetria, amely leképezi az egyik élt a másikra, de van néhány csúcspár, amelyre nincs szimmetria. amely leképezi az egyik csúcsot a másikra.
A félszimmetrikus gráfnak bipartitnak kell lennie , és automorfizmuscsoportjának tranzitívan kell hatnia a kétrészes gráf két csúcsrészére. Például az ábrán látható Folkman-gráfban a zöld csúcsok semmilyen automorfizmussal nem képezhetők le vörösre, de bármely két azonos színű csúcs szimmetrikus egymáshoz képest.
A félszimmetrikus gráfokat először Dauber, Frank Harari tanítványa tanulmányozta egy ma elérhetetlen „On line- but not point-symmetric graphs” című tanulmányában. A papírt John Folkman látta, akinek 1967-ben megjelent írása tartalmazta a legkisebb félszimmetrikus gráfot, amely ma Folkman -gráfként ismert , 20 csúcsával [1] . A "félszimmetrikus" kifejezést Klin, Lauri és Ziv-Av használta először egy 1978-ban publikált cikkében [2] .
A legkisebb köbös félszimmetrikus gráf (azaz olyan gráf, amelyben minden csúcs pontosan három élre esik) az 54 csúcsból álló Gray gráf . Bower [3] volt az első, aki felfedezte, hogy a gráf félszimmetrikus . Azt a tényt, hogy a gráf a legkisebb a köbös félszimmetrikus gráfok között, Marusic és Malnich [4] bizonyította .
Minden köbös félszimmetrikus gráf 768 csúcsig ismert. Konder, Malnic, Marusic és Potochnik szerint a négy legkisebb köbös félszimmetrikus gráf a Gray -gráf után a 110 csúcsos Ivanov-Iofinova gráf , a 112 csúcsú Ljubljana-gráf [5] , a 120 csúcsos gráf 8-as kerülettel, és a 12 sejtes Tatta [6] .