Vertexně-tranzitivní graf

V teorii grafů je vrcholově tranzitivní graf graf G takový, že pro libovolné dva vrcholy v 1 a v 2 grafu G existuje automorfismus

takové, že

Jinými slovy, graf je vertex-tranzitivní, pokud jeho skupina automorfismu působí tranzitivně vzhledem k vrcholům [1] . Graf je vertex-tranzitivní právě tehdy, když jsou výsledky automorfismů jeho doplňku shodné.

Jakýkoli symetrický graf bez izolovaných vrcholů je vertex-tranzitivní a každý vertex-tranzitivní graf je regulární . Ne všechny vertex-tranzitivní grafy jsou však symetrické (například hrany zkráceného čtyřstěnu ) a ne všechny pravidelné grafy jsou vertex-tranzitivní (například Fruchtův graf a Tietzeův graf ).

Příklady konečných grafů

Sada konečných vertex-tranzitivních grafů zahrnuje symetrické grafy (jako je Petersenův graf , Heawoodův graf a vrcholy a hrany pravidelných mnohostěnů ). Konečné Cayleyovy grafy (jako jsou krychlové cykly ) jsou vertex-tranzitivní, stejně jako vrcholy a hrany Archimedova tělesa (ačkoli pouze 2 z nich jsou symetrické). Potočnik, Spiga a Verret vytvořili soupis všech spojených kubických (tedy s vrcholy stupně 3) vertex-tranzitivních grafů s počtem vrcholů nepřesahujícím 1280 [2] .

Vlastnosti

Hranová konektivita vertex-tranzitivního grafu je rovna stupni d , zatímco konektivita vertexu bude alespoň 2( d +1)/3 [3] . Pokud je stupeň 4 nebo méně, nebo je graf také přechodově přechodný , nebo je grafem minimální Cayleyův graf , pak bude vrcholová konektivita d [4] .

Příklady nekonečných grafů

Nekonečné vertex-tranzitivní grafy zahrnují:

Dva spočetné vertex-tranzitivní grafy se nazývají kvaziizometrické , pokud je poměr jejich vzdálenostních funkcí ohraničen zdola a shora. Známá domněnka tvrdí, že jakýkoli nekonečný vertex-tranzitivní graf je kvazi-izomorfní s Cayleyovým grafem . Protipříklad předložili Reinhard Diestel a Imre Leader v roce 2001 [ 5] . V roce 2005 Eskin, Fisher a Whyte potvrdili správnost protipříkladu [6] .

Viz také

Poznámky

  1. ↑ Chris Godsil, Gordon Royle. Algebraická teorie grafů. - New York: Springer-Verlag, 2001. - T. 207 .
  2. ↑ Potočnik P., Spiga P. a Verret G. (2012), Kubické vertex-tranzitivní grafy až na 1280 vrcholech , Journal of Symbolic Computation 
  3. ↑ Godsil, C. a Royle, G. Teorie algebraických grafů. — Springer Verlag, 2001.
  4. ↑ Babai, L. Technická zpráva TR-94-10. - University of Chicago, 1996 . Získáno 29. srpna 2010. Archivováno z originálu 11. června 2010.
  5. ↑ Reinhard Diestel, Imre Leader. Dohad o limitě ne-Cayleyho grafů // Journal of Algebraic Combinatorics. - 2001. - T. 14 , no. 1 . — S. 17–25 . - doi : 10.1023/A:1011257718029 .
  6. ↑ Alex Eskin, David Fisher, Kevin Whyte. Kvazisometrie a rigidita řešitelných grup. — 2005.

Odkazy