Éltranzitív gráf

Ez a szócikk az éltranzitivitás gráfelméleti vonatkozásáról szól. A geometriai éltranzitivitáshoz lásd a sokszög szócikket.

Gráfcsaládok automorfizmusukkal meghatározva
távolságtranzitív	$\mathit{\to }$	távolságreguláris	$\mathit{\leftarrow }$	erősen reguláris
$\mathit{\downarrow }$
szimmetrikus	$\mathit{\leftarrow }$	t-tranzitív, t ≥ 2		ferdeszimmetrikus
$\mathit{\downarrow }$
(ha összefüggő) csúcs- és éltranzitív	$\mathit{\to }$	éltranzitív és reguláris	$\mathit{\to }$	éltranzitív
$\mathit{\downarrow }$		$\mathit{\downarrow }$		$\mathit{\downarrow }$
csúcstranzitív	$\mathit{\to }$	reguláris	$\mathit{\to }$	(ha páros) bireguláris
$\mathit{\uparrow }$
Cayley-gráf	$\mathit{\leftarrow }$	zérószimmetrikus		aszimmetrikus

A matematika, azon belül a gráfelmélet területén egy G gráf éltranzitív, ha bármely két e₁ és e₂ élére létezik G-nek olyan automorfizmusa, amely e₁-et e₂-be viszi át.

Más szavakkal egy gráf akkor éltranzitív, ha automorfizmus-csoportja tranzitívan hat az éleire nézve.

Példák és tulajdonságok

A Gray-gráf éltranzitív és reguláris, de nem csúcstranzitív.

Az éltranzitív gráfok közé tartozik az összes $K_{m,n}$ teljes páros gráf, az összes szimmetrikus gráf, pl. a kocka csúcsai és élei is éltranzitív gráfot alkotnak. A szimmetrikus gráfok csúcstranzitívek is (már ha összefüggőek), de általában véve az éltranzitív gráfok nem szükségképpen csúcstranzitívak. A Gray-gráf példa olyan gráfra, ami éltranzitív, de nem csúcstranzitív. Az összes ilyen gráf páros, ezért két színnel színezhető.

Az olyan éltranzitív gráfokat, amik regulárisak de nem csúcstranzitívak, félszimmetrikus gráfoknak nevezik. A Gray-gráf erre is példát szolgáltat. Minden éltranzitív gráf, ami nem csúcstranzitív, szükségképpen páros gráf és vagy félszimmetrikus vagy bireguláris.

Kapcsolódó szócikkek

• Éltranzitív (mértani jelentése)

További információk

• Sablon:MathWorld