É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]
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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Gray_graph_2COL.svg/200px-Gray_graph_2COL.svg.png)
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ó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