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

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 zérószimmetrikus gráf, 18 csúccsal és 27 éllel
A legkisebb zérószimmetrikus gráf, 18 csúccsal és 27 éllel
A csonkított kuboktaéder, egy zérószimmetrikus test
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.[3]

PéldákSzerkesztés

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]

TulajdonságokSzerkesztés

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.

Kapcsolódó szócikkekSzerkesztés

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

JegyzetekSzerkesztés

  1. Coxeter, Harold Scott MacDonald; Frucht, Roberto & Powers, David L. (1981), Zero-symmetric graphs, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, ISBN 0-12-194580-4
  2. (Coxeter, Frucht & Powers 1981), p. 4.
  3. (Coxeter, Frucht & Powers 1981), p. ix.
  4. (Coxeter, Frucht & Powers 1981), Figure 1.1, p. 5.
  5. (Coxeter, Frucht & Powers 1981), pp. 75 and 80.
  6. (Coxeter, Frucht & Powers 1981), p. 55.
  7. Potočnik, Primož; Spiga, Pablo & Verret, Gabriel (2013), "Cubic vertex-transitive graphs on up to 1280 vertices", Journal of Symbolic Computation 50: 465–477, DOI 10.1016/j.jsc.2012.09.002.
  8. (Coxeter, Frucht & Powers 1981), p. 10.