En semisymmetrisk graf är en oriktad kanttransitiv vanlig graf som inte är vertextransitiv . Med andra ord är en graf semisymmetrisk om varje vertex har samma antal infallande kanter och för varje par av kanter finns det en symmetri som mappar en kant till en annan, men det finns ett par av hörn för vilka det inte finns någon symmetri som mappar en vertex till en annan.
En semisymmetrisk graf måste vara bipartit , och dess automorfismgrupp måste agera transitivt på var och en av de två vertexdelarna av den bipartita grafen. Till exempel, i Folkman-grafen som visas i diagrammet, kan gröna hörn inte mappas till röda av någon automorfism, men vilka två hörn som helst av samma färg är symmetriska i förhållande till varandra.
Semisymmetriska grafer studerades först av Dauber, en elev till Frank Harari , i ett nu otillgängligt papper med titeln "On line-but not point-symmetric graphs". Tidningen sågs av John Folkman, vars papper, publicerad 1967, inkluderade den minsta semisymmetriska grafen, nu känd som Folkman Graph , med 20 hörn [1] . Termen "semisymmetrisk" användes först av Klin, Lauri och Ziv-Av i en tidning som de publicerade 1978 [2] .
Den minsta kubiska semisymmetriska grafen (det vill säga en graf där varje vertex faller mot exakt tre kanter) är Gray -grafen med 54 vertex . Bower [3] var den första som upptäckte att en graf är semisymmetrisk . Det faktum att grafen är den minsta bland kubiska semisymmetriska grafer bevisades av Marusic och Malnich [4] .
Alla kubiska semisymmetriska grafer upp till 768 hörn är kända. Enligt Konder, Malnic, Marusic och Potochnik är de fyra minsta kubiska semisymmetriska graferna efter den grå grafen Ivanov-Iofinova- grafen med 110 hörn , Ljubljana-grafen med 112 hörn [5] , grafen med 120 hörn med omkrets 8, och 12-cells Tatta [6] .