Puolisymmetrinen graafi on suuntaamaton reunatransitiivinen säännöllinen graafi , joka ei ole kärkitransitiivinen . Toisin sanoen graafi on puolisymmetrinen, jos jokaisessa kärjessä on sama määrä sattuvia reunoja ja jokaisella reunaparilla on symmetria, joka kuvaa yhden reunan toiseen, mutta on jokin kärkipari, jolle ei ole symmetriaa. joka kartoittaa yhden kärjen toiseen.
Puolisymmetrisen graafin on oltava kaksiosainen , ja sen automorfismiryhmän tulee toimia transitiivisesti molemmissa kaksiosaisen graafin kärkiosissa. Esimerkiksi kaaviossa esitetyssä Folkman-graafissa vihreitä pisteitä ei voi kartoittaa punaiseksi millään automorfismilla, vaan mitkä tahansa kaksi samanväristä kärkeä ovat symmetrisiä toistensa suhteen.
Puolisymmetrisiä kaavioita tutki ensimmäisenä Dauber, Frank Hararin oppilas , nyt saatavilla olevassa artikkelissa "On line- but not point-symmetric graphs". Paperin näki John Folkman, jonka vuonna 1967 julkaistu paperi sisälsi pienimmän puolisymmetrisen graafin, joka tunnetaan nykyään nimellä Folkman Graph , jossa on 20 kärkeä [1] . Termiä "puolisymmetrinen" käyttivät ensimmäisenä Klin, Lauri ja Ziv-Av vuonna 1978 julkaisemassaan artikkelissa [2] .
Pienin kuutioinen puolisymmetrinen graafi (eli graafi, jossa kukin kärki osuu täsmälleen kolmeen reunaan) on 54-pisteinen Gray-graafi . Bower [3] havaitsi ensimmäisenä, että graafi on puolisymmetrinen . Marusic ja Malnich osoittivat, että graafi on pienin kuutiopuolisymmetrisistä graafista [4] .
Kaikki kuutioiset puolisymmetriset graafit 768 kärkeen asti tunnetaan. Konderin, Malnicin, Marusicin ja Potochnikin mukaan neljä pienintä kuutiometristä puolisymmetristä graafia Gray -graafin jälkeen ovat 110-pisteinen Ivanov-Iofinova- graafi , 112- pisteinen Ljubljana-graafi [5] , 120-pisteinen graafi, jonka ympärysmitta on 8, ja 12-soluinen Tatta [6] .