matematikai fogalom a gráfelméletben From Wikipedia, the free encyclopedia
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.[1] Ezekben a gráfokban bármely két u és v csúcshoz pontosan egy, az u-t v-be átvivő automorfizmus tartozik.[2]
A gráfosztálynak R. M. Foster adott nevet H. S. M. Coxeternek írt, 1966-os levelében.[3]
A legkisebb zérószimmetrikus gráf egy 18 csúcsú, síkba nem rajzolható gráf.[4] 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.[5]
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.[6]
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.[7]
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.[8] 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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.