Félszimmetrikus gráf

Gráfcsaládok automorfizmusukkal meghatározva
távolságtranzitív	${\boldsymbol {\rightarrow }}$	távolságreguláris	${\boldsymbol {\leftarrow }}$	erősen reguláris
${\boldsymbol {\downarrow }}$
szimmetrikus	${\boldsymbol {\leftarrow }}$	t-tranzitív, t ≥ 2		ferdeszimmetrikus
${\boldsymbol {\downarrow }}$
(ha összefüggő) csúcs- és éltranzitív	${\boldsymbol {\rightarrow }}$	éltranzitív és reguláris	${\boldsymbol {\rightarrow }}$	éltranzitív
${\boldsymbol {\downarrow }}$		${\boldsymbol {\downarrow }}$		${\boldsymbol {\downarrow }}$
csúcstranzitív	${\boldsymbol {\rightarrow }}$	reguláris	${\boldsymbol {\rightarrow }}$	(ha páros) bireguláris
${\boldsymbol {\uparrow }}$
Cayley-gráf	${\boldsymbol {\leftarrow }}$	zérószimmetrikus		aszimmetrikus

A legkisebb félszimmetrikus gráf, a Folkman-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.

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 (Bouwer 1968) 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

• 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 és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További információk

• Weisstein, Eric W.: Semisymmetric Graph (angol nyelven). Wolfram MathWorld