Csúcstranzitív gráf

A Wikipédiából, a szabad enciklopédiából
Minden Cayley-gráf csúcstranzitív és minden csúcstranzitív gráf reguláris

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 | forrásszöveg szerkesztése]

Véges példák[szerkesztés | forrásszöveg szerkesztése]

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

Végtelen példák[szerkesztés | forrásszöveg szerkesztése]

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

Lásd még[szerkesztés | forrásszöveg szerkesztése]

Irodalom[szerkesztés | forrásszöveg szerkesztése]

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