„Éltranzitív gráf” változatai közötti eltérés

Tartalom törölve Tartalom hozzáadva

Sorban

A lap 2016. május 17., 12:42-kori változata

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

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

Más szavakkal egy gráf akkor éltranzitív, ha automorfizmus-csoportja tranzitív 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 alkotnak.^[1] 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,^[1] 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.^[2]

Kapcsolódó szócikkek

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

Jegyzetek

↑ ^a ^b ^c Biggs, Norman. Algebraic Graph Theory, 2nd, Cambridge: Cambridge University Press, 118. o. (1993). ISBN 0-521-45897-8
↑ Lauri, Josef & Scapellato, Raffaele (2003), Topics in Graph Automorphisms and Reconstruction, London Mathematical Society Student Texts, Cambridge University Press, pp. 20–21, ISBN 9780521529037, <http://books.google.com/books?id=hsymFm0E0uIC&pg=PA20>.

További információk

Weisstein, Eric W.: Edge-transitive graph (angol nyelven). Wolfram MathWorld

[biggs-1] Biggs, Norman. Algebraic Graph Theory, 2nd, Cambridge: Cambridge University Press, 118. o. (1993). ISBN 0-521-45897-8

[ls03-2] Lauri, Josef & Scapellato, Raffaele (2003), Topics in Graph Automorphisms and Reconstruction, London Mathematical Society Student Texts, Cambridge University Press, pp. 20–21, ISBN 9780521529037, <http://books.google.com/books?id=hsymFm0E0uIC&pg=PA20>.

[1]

[2]

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