Hraně tranzitivní graf

V teorii grafů je hrana - tranzitivní graf G , pro kterékoli dvě hrany, z nichž e 1 a e 2 existuje automorfismus , který zobrazuje e 1 až e 2 [1] .  

Jinými slovy, graf je přechodově přechodný, pokud jeho skupina automorfismu působí přechodně na jeho hranách.

Příklady a vlastnosti

Hraně-tranzitivní grafy zahrnují všechny kompletní bipartitní grafy a všechny symetrické grafy , jako jsou vrcholy a hrany krychle [1] . Symetrické grafy jsou také vertex-tranzitivní (pokud jsou spojeny), ale obecně hranově-tranzitivní grafy nemusí být nutně vertex-tranzitivní. Grayův graf je příkladem grafu, který je hranově tranzitivní, ale ne vertexově tranzitivní. Všechny tyto grafy jsou bipartitní [1] , a proto mohou být vybarveny pouze dvěma barvami.

Hraně tranzitivní graf, který je také pravidelný , ale není vertexově tranzitivní, se nazývá polosymetrický . Jako příklad slouží opět hrabě Gray . Hranový tranzitivní graf musí být bipartitní a buď semisymetrický, nebo biregulární [2]

Viz také

Poznámky

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


Literatura

Odkazy