É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 → {\displaystyle {\boldsymbol {\rightarrow }}} távolságreguláris ← {\displaystyle {\boldsymbol {\leftarrow }}} erősen reguláris
↓ {\displaystyle {\boldsymbol {\downarrow }}}
szimmetrikus ← {\displaystyle {\boldsymbol {\leftarrow }}} t-tranzitív, t ≥ 2ferdeszimmetrikus
↓ {\displaystyle {\boldsymbol {\downarrow }}}
(ha összefüggő)
csúcs- és éltranzitív		 → {\displaystyle {\boldsymbol {\rightarrow }}} éltranzitív és reguláris → {\displaystyle {\boldsymbol {\rightarrow }}} éltranzitív
↓ {\displaystyle {\boldsymbol {\downarrow }}} ↓ {\displaystyle {\boldsymbol {\downarrow }}} ↓ {\displaystyle {\boldsymbol {\downarrow }}}
csúcstranzitív → {\displaystyle {\boldsymbol {\rightarrow }}} reguláris → {\displaystyle {\boldsymbol {\rightarrow }}} (ha páros)
bireguláris
↑ {\displaystyle {\boldsymbol {\uparrow }}}
Cayley-gráf ← {\displaystyle {\boldsymbol {\leftarrow }}} zérószimmetrikusaszimmetrikus

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

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 {\displaystyle 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.[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

Jegyzetek

  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ók