Csúcstranzitív gráf

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

• Minden csúcstranzitív gráf reguláris.
• Csúcstranzitív gráf komplementere is csúcstranzitív.

Véges példák

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

• 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 $K_{n,n}$ 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.

Lásd még

• Lovász-sejtés

Irodalom

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