Csúcstranzitív gráf

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.

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
Minden Cayley-gráf csúcstranzitív és minden csúcstranzitív gráf reguláris

Elemi tulajdonságokSzerkesztés

Véges példákSzerkesztés

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

Végtelen példákSzerkeszté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ócikkekSzerkesztés

IrodalomSzerkesztés

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