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.

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

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.

Kapcsolódó szócikkek

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

Irodalom

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