Vrcholově přechodný graf - Vertex-transitive graph - Wikipedia

Skupiny grafů definované jejich automorfismy
vzdálenost-tranzitivní→vzdálenost-pravidelná←velmi pravidelné
↓
symetrický (oblouk-tranzitivní)←t-tranzitivní, t ≥ 2šikmo symetrický
↓
(je-li připojen)
vrchol a hrana-tranzitivní		→hrana-tranzitivní a pravidelná→hrana tranzitivní
↓↓↓
vrchol-tranzitivní→pravidelný→(pokud je bipartitní)
biregular
↑
Cayleyův graf←nulově symetrickýasymetrický

V matematický pole teorie grafů, a vrchol-tranzitivní graf je graf G ve kterém, vzhledem k jakýmkoli dvěma vrcholům proti1 a proti2 z G, některé jsou automorfismus

takhle

Jinými slovy, graf je vrcholný, pokud je automorfická skupina činy přechodně na jeho vrcholech.[1] Graf je vrcholný kdyby a jen kdyby své doplněk grafu je, protože skupinové akce jsou totožné.

Každý symetrický graf bez izolované vrcholy je vrchol-tranzitivní a každý vrcholný graf je pravidelný. Ne všechny vrcholné grafy jsou však symetrické (například hrany zkrácený čtyřstěn ) a ne všechny běžné grafy jsou vrcholné (například Frucht graf a Tietzeův graf ).

Konečné příklady

Okraje zkrácený čtyřstěn tvoří vrchol-tranzitivní graf (také a Cayleyův graf ) což není symetrický.

Konečné vrcholové tranzitivní grafy zahrnují symetrické grafy (tak jako Petersenův graf, Heawoodův graf a vrcholy a hrany Platonické pevné látky ). Konečný Cayleyovy grafy (jako cykly spojené s krychlí ) jsou také vertex-transitive, stejně jako vrcholy a hrany Archimédovy pevné látky (i když pouze dva z nich jsou symetrické). Potočnik, Spiga a Verret zkonstruovali sčítání všech připojených kubických vrcholně přechodných grafů na maximálně 1280 vrcholech.[2]

Ačkoli každý Cayleyův graf je vrcholný, existují i ​​jiné vrcholně přechodné grafy, které nejsou Cayleyovými grafy. Nejznámějším příkladem je Petersenův graf, ale lze sestavit i jiné, včetně spojnicové grafy z hrana tranzitivní ne-bipartitní grafy s zvláštní stupně vrcholů.[3]

Vlastnosti

The okrajová konektivita vertex-tranzitivního grafu se rovná stupeň d, zatímco vrcholná konektivita bude minimálně 2 (d + 1)/3.[4]Pokud je stupeň 4 nebo méně, nebo je také graf hrana tranzitivní, nebo je graf minimální Cayleyův graf, pak se bude konektivita vrcholů rovnat d.[5]

Nekonečné příklady

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

Dva počitatelný vrchol-tranzitivní grafy se nazývají kvazi-izometrický pokud je poměr jejich funkce vzdálenosti je ohraničen zdola a shora. Dobře známý dohad uvedl, že každý nekonečný vrcholný graf je kvazi-izometrický k a Cayleyův graf. Protějšek navrhl Diestel a Vůdce v roce 2001.[6] V roce 2005 Eskin, Fisher a Whyte potvrdili protiklad.[7]

Viz také

Reference

  1. ^ Godsil, Chris; Royle, Gordone (2001), Algebraická teorie grafů, Postgraduální texty z matematiky, 207, New York: Springer-Verlag.
  2. ^ Potočnik P., Spiga P. & Verret G. (2013), „Cubic vertex-transitive graphs on up to 1280 vertices“, Journal of Symbolic Computation, 50: 465–477, arXiv:1201.5317, doi:10.1016 / j.jsc.2012.09.002.
  3. ^ Lauri, Josef; Scapellato, Raffaele (2003), Témata v automatických grafech a rekonstrukcích Studentské texty London Mathematical Society, 54, Cambridge: Cambridge University Press, str. 44, ISBN  0-521-82151-7, PAN  1971819. Lauri a Scapelleto připisují tuto konstrukci Markovi Watkinsovi.
  4. ^ Godsil, C. & Royle, G. (2001), Algebraická teorie grafůSpringer Verlag
  5. ^ Babai, L. (1996), Technická zpráva TR-94-10, University of Chicago[1] Archivováno 11.06.2010 na Wayback Machine
  6. ^ Diestel, Reinhard; Vůdce, Imre (2001), „Domněnka týkající se limitu jiných než Cayleyových grafů“ (PDF), Journal of Algebraic Combinatorics, 14 (1): 17–25, doi:10.1023 / A: 1011257718029.
  7. ^ Eskin, Alex; Fisher, David; Whyte, Kevin (2005). "Kvazi-izometrie a tuhost řešitelných skupin". arXiv:math.GR/0511647..

externí odkazy