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 \boldsymbol{\rightarrow} távolságreguláris \boldsymbol{\leftarrow} erősen reguláris
\boldsymbol{\downarrow}
szimmetrikus \boldsymbol{\leftarrow} t-tranzitív, t ≥ 2 ferdeszimmetrikus
\boldsymbol{\downarrow}
(ha összefüggő)
csúcs- és éltranzitív
\boldsymbol{\rightarrow} éltranzitív és reguláris \boldsymbol{\rightarrow} éltranzitív
\boldsymbol{\downarrow} \boldsymbol{\downarrow} \boldsymbol{\downarrow}
csúcstranzitív \boldsymbol{\rightarrow} reguláris \boldsymbol{\rightarrow} (ha páros)
bireguláris
\boldsymbol{\uparrow}
Cayley-gráf \boldsymbol{\leftarrow} 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)