Zérószimmetrikus gráf

A matematika, azon belül a gráfelmélet területén egy zérószimmetrikus gráf (zero-symmetric graph) olyan összefüggő gráf, melynek csúcsai egymással páronként szimmetrikusak, minden csúcs pontosan három élen van rajta, ezek az élek viszont egymással páronként nem szimmetrikusak. Precízebben megfogalmazva, olyan összefüggő csúcstranzitív 3-reguláris gráf, melynek éleit az automorfizmus-csoport három különböző pályára particionálja. Ezekben a gráfokban bármely két u és v csúcshoz pontosan egy, az u-t v-be átvivő automorfizmus tartozik.

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 zérószimmetrikus gráf, 18 csúccsal és 27 éllel

A csonkított kuboktaéder, egy zérószimmetrikus test

A gráfosztálynak R. M. Foster adott nevet H. S. M. Coxeternek írt, 1966-os levelében.

Példák

A legkisebb zérószimmetrikus gráf egy 18 csúcsú, síkba nem rajzolható gráf. LCF-jelölése [5,−5]⁹.

A síkbarajzolható gráfok közül a csonkított kuboktaéder és a csonkított ikozidodekaéder gráfjai is zérószimmetrikusak.

Ezek a példák mind páros gráfok voltak. Léteznek azonban nagyobb méretű zérószimmetrikus gráfok, melyek nem párosak.

Tulajdonságok

Minden zérószimmetrikus gráf Cayley-gráf, ami a 3-reguláris csúcstranzitív gráfokra nem igaz általánosságban; ez a tulajdonság segít a zérószimmetrikus gráfok leszámlálásában. 1280 csúcsig bezárólag 97 687 3-reguláris zérószimmetrikus gráf létezik. Az említett mérettartományban a zérószimmetrikus gráfok alkotják a 3-reguláris Cayley-gráfok 89%-át és az összefüggő csúcstranzitív 3-reguláris gráfok 88%-át.

A matematika megoldatlan problémája: Van-e minden véges zérószimmetrikus gráfnak Hamilton-köre? (A matematika további megoldatlan problémái)

Minden eddig ismert véges összefüggő zérószimmetrikus gráfnak van Hamilton-köre, de nem ismert, hogy ez minden zérószimmetrikus gráfra igaz-e. Ez a Lovász-sejtés speciális esete, miszerint (öt ismert kivétellel, melyek egyike sem zérószimmetrikus) minden véges összefüggő csúcstranzitív gráf, továbbá minden véges Cayley-gráf rendelkezik Hamilton-körrel.

Kapcsolódó szócikkek

• Félszimmetrikus gráfok, olyan gráfok, melyek bármely két éle között szimmetria van, de bármely két csúcsa között nincsen (megfordítva az élek és csúcsok szerepét a zérószimmetrikus gráfok definíciójában)

Fordítás

• Ez a szócikk részben vagy egészben a Zero-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.