Csúcstranzitív gráf
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 |
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
- Minden csúcstranzitív gráf reguláris.
- Csúcstranzitív gráf komplementere is csúcstranzitív.
Véges példák
- Minden Kneser-gráf és azok komplementerei, a Johnson-gráfok csúcstranzitívak.
- Speciális Kneser-gráfként a Petersen-gráf is csúcstranzitív.
- A véges Cayley-gráfok csúcstranzitívak.
- A szabályos testek élgráfjai csúcstranzitívak.
- Minden hiperkocka élgráfja csúcstranzitív.
- Minden teljes gráf csúcstranzitív.
- A gráfok, tehát az azonos számosságú osztályokkal rendelkező teljes páros gráfok is csúcstranzitívak.
- A körgráfok szintén csúcstranzitívak.
- Csúcstranzitívak a gyűrűs kockák is.
Végtelen példák
- 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
Irodalom
- Godsil, C. and Royle, G.. Algebraic Graph Theory. Springer Verlag (2001)