A matematika, azon belül a gráfelmélet területén egy félszimmetrikus gráf vagy szemiszimmetrikus gráf (semi-symmetric graph) olyan irányítatlan gráf, ami reguláris, éltranzitív, de nem csúcstranzitív. Más megfogalmazásban, egy gráf akkor félszimmetrikus, ha minden csúcsból ugyanannyi él indul ki, és létezik a gráf bármely élét bármely más élébe átvivő szimmetria, de létezik olyan csúcspár, melynek egyik csúcsát a másikba nem viszi át szimmetria.
Tulajdonságok Egy félszimmetrikus gráf mindig páros, és automorfizmus-csoportja tranzitívan hat a bipartíció mindkét oldalán. Például az ábrán látható Folkman-gráf zöld csúcsai nem vihetők át automorfizmussal a piros csúcsokba, de bármely két, megegyező színű csúcs átvihető egymásba (szimmetrikusak).
Története A félszimmetrikus gráfokat először F. Harary egy tanítványa, E. Dauber tanulmányozta, On line- but not point-symmetric graphs című, már nem hozzáférhető cikkében. Ezzel a cikket találkozott Jon Folkman, akinek 1967-es publikációjában szerepelt a legkisebb, 20 csúccsal rendelkező félszimmetrikus gráf is, ami jelenleg Folkman-gráf néven ismert.. A „semi-symmetric” kifejezést először Klin et al. használták 1978-as cikkükben. 3-reguláris gráfok A legkisebb 3-reguláris félszimmetrikus gráf az 54 csúcsú Gray-gráf. A félszimmetrikusságot figyelte meg, azt, hogy ez a legkisebb 3-reguláris félszimmetrikus gráf, Dragan Marušič és Aleksander Malnič igazolták.. Egészen 768 csúcsig az összes 3-reguláris félszimmetrikus gráf ismert. Conder, Malnič, Marušič és Potočnik szerint a Gray-gráf után következő négy legkisebb ilyen gráf a 110 csúcsú Iofinova–Ivanov-gráf, a 112 csúcsú Ljubljana-gráf,. egy 120 csúcsú és 8 girthű gráf, valamint a Tutte 12-cage..
Fordítás
Jegyzetek
További információk
Kategória:Algebrai gráfelmélet Kategória:Gráfcsaládok Kategória:Reguláris gráfok