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

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

Gráfcsaládok automorfizmusukkal meghatározva
távolságtranzitívtávolságreguláriserősen reguláris
szimmetrikust-tranzitív, t ≥ 2ferdeszimmetrikus
(ha összefüggő)
csúcs- és éltranzitív
éltranzitív és reguláriséltranzitív
csúcstranzitívreguláris(ha páros)
bireguláris
Cayley-gráfzérószimmetrikusaszimmetrikus

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

Példák és tulajdonságokSzerkesztés

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

Az éltranzitív gráfok közé tartozik az összes   teljes páros gráf, az összes szimmetrikus gráf, pl. a kocka csúcsai és élei is éltranzitív gráfot 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ócikkekSzerkesztés

JegyzetekSzerkesztés

  1. a b c Biggs, Norman. Algebraic Graph Theory, 2nd, Cambridge: Cambridge University Press, 118. o. (1993). ISBN 0-521-45897-8 
  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>.

További információkSzerkesztés