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.
Elemi tulajdonságok[szerkesztés]
- Minden csúcstranzitív gráf reguláris.
- Csúcstranzitív gráf komplementere is csúcstranzitív.
Véges példák[szerkesztés]
- 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[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)