Féltranzitív gráf

A matematika, azon belül a gráfelmélet területén egy G gráf féltranzitív, ha egyszerre csúcs- és éltranzitív, de nem szimmetrikus.[1] Más szavakkal, egy gráf akkor féltranzitív, ha automorfizmus-csoportja tranzitív módon hat a csúcsaira és az éleire is, de nem hat tranzitívan a szomszédos csúcsok rendezett párjaira nézve.

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
A Holt-gráf a legkisebb féltranzitív gráf. A rajzból látható a tükörszimmetria hiánya, ami aláhúzza, hogy az élek nem ekvivalensek inverzeikkel.

Minden összefüggő szimmetrikus gráf csúcs- és éltranzitív, páratlan fokú gráfokra az állítás megfordítása is igaz,[2] tehát páratlan fokszámú féltranzitív gráfok nem léteznek. Léteznek azonban páros fokszámú féltranzitív gráfok.[3] A legkisebb féltranzitív gráf a Holt-gráf, 4-es fokszámmal és 27 csúccsal.[4][5]

JegyzetekSzerkesztés

  1. Gross, J.L. and Yellen, J.. Handbook of Graph Theory. CRC Press, 491. o. (2004). ISBN 1-58488-090-2 
  2. Babai, L. Handbook of Combinatorics. Elsevier (1996) 
  3. Bouwer, Z. "Vertex and Edge Transitive, But Not 1-Transitive Graphs." Canad. Math. Bull. 13, 231–237, 1970.
  4. Biggs, Norman. Algebraic Graph Theory, 2nd, Cambridge: Cambridge University Press (1993). ISBN 0-521-45897-8 
  5. Holt, Derek F. (1981). „A graph which is edge transitive but not arc transitive”. Journal of Graph Theory 5 (2), 201–204. o. DOI:10.1002/jgt.3190050210.  .