Éltranzitív gráf

A gráfelméletben az éltranzitív egy G gráf  , amelynek bármely két élére e 1 és e 2 van egy automorfizmus , amely e 1 - et e 2 -re képez le [1] .

Más szóval, egy gráf éltranzitív, ha az automorfizmuscsoportja tranzitívan hat az éleire.

Példák és tulajdonságok

Az éltranzitív gráfok közé tartozik az összes teljes kétrészes gráf és minden szimmetrikus gráf , például egy kocka csúcsai és élei [1] . A szimmetrikus gráfok is csúcstranzitívak ( ha össze vannak kötve), de általában az éltranzitív gráfok nem feltétlenül csúcstranzitívak. A Gray gráf egy olyan gráf példa, amely éltranzitív, de nem csúcstranzitív. Minden ilyen gráf kétoldalas [1] , ezért csak két színnel lehet színezni .

Egy éltranzitív gráfot, amely szintén szabályos , de nem csúcstranzitív, félszimmetrikusnak nevezzük . Gray gróf ismét példaként szolgál. Az éltranzitív gráfnak kétrészesnek és félszimmetrikusnak vagy biregulárisnak kell lennie [2]

Lásd még

• Éltranzitivitás (geometriában)

Jegyzetek

1. ↑ 1 2 3 Biggs, 1993 , p. 118.
2. ↑ Lauri, 2003 , p. 20-21.

Irodalom

• Biggs N. Algebrai gráfelmélet  . — 2. kiadás. - Cambridge, 1993. - ISBN 0-521-45897-8 .
• Lauri J. , Scapellato R. Gráfautomorfizmusok és rekonstrukció témái  . - Cambridge University Press, 2003. - Vol. 54. - (Londoni Matematikai Társaság. Diákszövegek). — ISBN 9780521529037 .

Linkek

• Weisstein, Eric W. Éltranzitív gráf  (angol) a Wolfram MathWorld webhelyen .