Csúcstranzitív gráf

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

• Minden csúcstranzitív gráf reguláris.
• Csúcstranzitív gráf komplementere 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 ${\displaystyle 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.

• 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.

• Éltranzitív gráf
• Lovász-sejtés

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