En semisymmetrisk graf er en urettet kanttransitiv regulær graf , der ikke er toppunkttransitiv . Med andre ord er en graf semisymmetrisk, hvis hvert toppunkt har det samme antal indfaldende kanter, og for hvert par af kanter er der en symmetri, der kortlægger en kant til en anden, men der er et par hjørner, for hvilket der ikke er nogen symmetri der kortlægger et toppunkt til et andet.
En semisymmetrisk graf skal være todelt , og dens automorfigruppe skal virke transitivt på hver af de to topdele af den todelte graf. For eksempel, i Folkman-grafen vist i diagrammet, kan grønne hjørner ikke kortlægges til røde af nogen automorfi, men to spidser af samme farve er symmetriske i forhold til hinanden.
Semisymmetriske grafer blev først studeret af Dauber, en elev af Frank Harari , i et nu utilgængeligt papir med titlen "On line-but not point-symmetric graphs". Papiret blev set af John Folkman, hvis papir, udgivet i 1967, indeholdt den mindste semisymmetriske graf, nu kendt som Folkman Graph , med 20 hjørner [1] . Udtrykket "semisymmetrisk" blev første gang brugt af Klin, Lauri og Ziv-Av i et papir, de udgav i 1978 [2] .
Den mindste kubiske semisymmetriske graf (det vil sige en graf, hvor hvert toppunkt falder ind på nøjagtig tre kanter) er den 54-punkts grå graf . Bower [3] var den første til at opdage, at en graf er semisymmetrisk . Det faktum, at grafen er den mindste blandt kubiske semisymmetriske grafer, blev bevist af Marusic og Malnich [4] .
Alle kubiske semisymmetriske grafer op til 768 hjørner er kendte. Ifølge Konder, Malnic, Marusic og Potochnik er de fire mindste kubiske semisymmetriske grafer efter den grå graf Ivanov-Iofinova- grafen med 110 toppunkter , Ljubljana-grafen med 112 toppunkter [5] og grafen med 120 toppunkter med omkreds 8, og 12-cellet Tatta [6] .