Félszimmetrikus gráf

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.

Gráfcsaládok automorfizmusukkal meghatározva
távolságtranzitívtávolságreguláriserősen reguláris
szimmetrikust-tranzitív, t ≥ 2ferdeszimmetrikus
(ha összefüggő)
csúcs- és éltranzitív
éltranzitív és reguláriséltranzitív
csúcstranzitívreguláris(ha páros)
bireguláris
Cayley-gráfzérószimmetrikusaszimmetrikus
A legkisebb félszimmetrikus gráf, a Folkman-gráf.

TulajdonságokSzerkesztés

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éneteSzerkesztés

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.[1] A „semi-symmetric” kifejezést először Klin et al. használták 1978-as cikkükben.[2]

3-reguláris gráfokSzerkesztés

A legkisebb 3-reguláris félszimmetrikus gráf az 54 csúcsú Gray-gráf. A félszimmetrikusságot (Bouwer 1968) figyelte meg, azt, hogy ez a legkisebb 3-reguláris félszimmetrikus gráf, Dragan Marušič és Aleksander Malnič igazolták.[3] 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,[4] egy 120 csúcsú és 8 girthű gráf, valamint a Tutte 12-cage.[5]

FordításSzerkesztés

  • Ez a szócikk részben vagy egészben a Semi-symmetric graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

JegyzetekSzerkesztés

  1. Folkman, J. (1967), "Regular line-symmetric graphs", Journal of Combinatorial Theory 3 (3): 215–232, DOI 10.1016/S0021-9800(67)80069-3.
  2. (2011. január 21.) „Links between two semisymmetric graphs on 112 vertices through the lens of association schemes”. (Hozzáférés ideje: 2015. augusztus 17.)  
  3. Bouwer, I. Z. (1968), "An edge but not vertex transitive cubic graph", Bulletin of the Canadian Mathematical Society 11: 533–535, DOI 10.4153/CMB-1968-063-0.
  4. Conder, M.; Malnič, A. & Marušič, D. et al. (2002), "The Ljubljana Graph", IMFM Preprints (Ljubljana: Institute of Mathematics, Physics and Mechanics) 40 (845), <http://www.imfm.si/preprinti/PDF/00845.pdf>.
  5. Conder, Marston; Malnič, Aleksander & Marušič, Dragan et al. (2006), "A census of semisymmetric cubic graphs on up to 768 vertices", Journal of Algebraic Combinatorics 23 (3): 255–294, DOI 10.1007/s10801-006-7397-3.

További információkSzerkesztés