Nulový symetrický graf - Zero-symmetric graph
V matematický pole teorie grafů, a nulový symetrický graf je připojený graf ve kterém má každý vrchol přesně tři dopadající hrany a pro každé dva vrcholy existuje jedinečný symetrie přičemž jeden vrchol na druhý. Takový graf je a vrchol-tranzitivní graf ale nemůže být hranový tranzitivní graf: počet symetrií se rovná počtu vrcholů, příliš málo na to, aby se každá hrana dostala ke každé druhé hraně.[1]
Název této třídy grafů vytvořil R. M. Foster v dopise z roku 1966 H. S. M. Coxeter.[2] Tyto grafy se dnes označují jako kubické GRR (Graphical Regular Representations). [3]
Příklady
Nejmenší graf nulové symetrie je neplanární graf s 18 vrcholy.[4] Své LCF notace je [5, −5]9.
Mezi rovinné grafy, zkrácený kuboctahedral a zkrácené icosidodecahedral grafy jsou také nulově symetrické.[5]
Tyto příklady jsou všechny bipartitní grafy. Existují však větší příklady nulově symetrických grafů, které nejsou bipartitní.[6]
Tyto příklady mají také tři různé třídy symetrie (oběžné dráhy) hran. Existují však nulové symetrické grafy pouze se dvěma oběžnými dráhami hran. Nejmenší takový graf má 20 vrcholů, s LCF notace [6,6,-6,-6]5.[7]
Vlastnosti
Každý konečný graf nulové symetrie je a Cayleyův graf, vlastnost, která ne vždy platí pro kubické vertexové tranzitivní grafy obecněji a která pomáhá při řešení kombinatorický výčet úkoly týkající se nulových symetrických grafů. K dispozici je 97687 nulových symetrických grafů až na 1280 vrcholech. Tyto grafy tvoří 89% kubických Cayleyových grafů a 88% všech připojených vrcholně přechodných kubických grafů na stejném počtu vrcholů.[8]
 | Nevyřešený problém v matematice: Obsahuje každý konečný graf nulové symetrie a Hamiltonovský cyklus ? (více nevyřešených úloh z matematiky) |
Všechny známé konečně spojené nulové symetrické grafy obsahují a Hamiltonovský cyklus, ale není známo, zda je každý konečně spojený graf nulové symetrie nutně hamiltoniánský.[9] Toto je zvláštní případ Lovász dohad že (až na pět známých výjimek, z nichž žádná není nulová symetrická) je každý konečně spojený vrchol-tranzitivní graf a každý konečný Cayleyův graf Hamiltonian.
Viz také
- Polosymetrický graf, grafy, které mají symetrii mezi dvěma hranami, ale ne mezi dvěma vrcholy (obrácení rolí hran a vrcholů v definici grafů s nulovou symetrií)
Reference
- ^ Coxeter, Harold Scott MacDonald; Frucht, Roberto; Powers, David L. (1981), Nulové symetrické grafy, Academic Press, Inc. [Harcourt Brace Jovanovich, vydavatelé], New York-Londýn, ISBN 0-12-194580-4, PAN 0658666
- ^ Coxeter, Frucht & Powers (1981), str. ix.
- ^ Lauri, Josef; Scapellato, Raffaele (2003), Témata v automatizaci grafů a rekonstrukci, London Mathematical Society Student Texts, Cambridge University Press, s. 20–21, ISBN 9780521529037.
- ^ Coxeter, Frucht & Powers (1981), Obrázek 1.1, s. 5.
- ^ Coxeter, Frucht & Powers (1981), s. 75 a 80.
- ^ Coxeter, Frucht & Powers (1981), str. 55.
- ^ Conder, Marston D. E.; Pisanski, Tomaž; Žitnik, Arjana (2017), „Vertex-transitive graphs and their arc-types“, Ars Mathematica Contemporanea, 12 (2): 383–413, arXiv:1505.02029, doi:10.26493 / 1855-3974.1146.f96, PAN 3646702
- ^ Potočnik, Primož; Spiga, Pablo; Verret, Gabriel (2013), „Kubické vertex-tranzitivní grafy až na 1280 vrcholech“, Journal of Symbolic Computation, 50: 465–477, arXiv:1201.5317, doi:10.1016 / j.jsc.2012.09.002, PAN 2996891.
- ^ Coxeter, Frucht & Powers (1981), str. 10.