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., p. 4.

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

Példák A legkisebb zérószimmetrikus gráf egy 18 csúcsú, síkba nem rajzolható gráf., Figure 1.1, p. 5. LCF-jelölése [5,−5]9.

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., pp. 75 and 80.

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., p. 55.

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 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..

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., p. 10. 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

Jegyzetek

Kategória:Algebrai gráfelmélet Kategória:Gráfcsaládok Kategória:Reguláris gráfok