Csúcstranzitív gráf

A Wikipédiából, a szabad enciklopédiából
Gráfcsaládok automorfizmusukkal meghatározva
távolságtranzitív távolságreguláris erősen reguláris
szimmetrikus t-tranzitív, t ≥ 2 ferdeszimmetrikus
(ha összefüggő)
csúcs- és éltranzitív
éltranzitív és reguláris éltranzitív
csúcstranzitív reguláris (ha páros)
bireguláris
Cayley-gráf zérószimmetrikus aszimmetrikus
Minden Cayley-gráf csúcstranzitív és minden csúcstranzitív gráf reguláris

A matematika, azon belül a gráfelmélet területén egy G=(V, E) gráf csúcstranzitív, ha minden u, v ∈ V csúcspárra létezik olyan f:V→V gráfautomorfizmus, amelyre f(u)=v.

Elemi tulajdonságok[szerkesztés]

Véges példák[szerkesztés]

Csonkított tetraéder élgráfja is csúcstranzitív

Végtelen példák[szerkesztés]

  • Minden végtelen Cayley-gráf csúcstranzitív.
  • Minden Bethe-rács Cayley-gráf, így szükségszerűen csúcstranzitív is.

Kapcsolódó szócikkek[szerkesztés]

Irodalom[szerkesztés]

  • Godsil, C. and Royle, G.. Algebraic Graph Theory. Springer Verlag (2001)