Toroidal graf - Toroidal graph

Image
En kubikkgraf med 14 hjørner innebygd på en torus
Image
Den Heawood grafen og tilhørende kart innleiret i torusen.

I matematikk er en toroidegraf en graf som kan legges inn på en torus . Med andre ord kan grafens hjørner plasseres på en torus slik at ingen kanter krysser.

Eksempler

Enhver graf som kan være innebygd i et plan, kan også være innebygd i en torus. En toroidegraf av slekt 1 kan være innebygd i en torus, men ikke i et plan. Den Heawood graf , den komplette grafen K 7 (og dermed K 5 og K 6 ), idet Petersen grafen (og dermed den fullstendige todeling grafen K 3,3 , ettersom den Petersen kurve som inneholder en underavdeling av den), en av de Blanuša snarks , og alle Möbius-stiger er toroidale. Mer generelt er enhver graf med kryss nummer 1 toroidal. Noen grafer med større kryssende tall er også toroidale: Möbius – Kantor-grafen har for eksempel kryss nummer 4 og er toroidal.

Eiendommer

Enhver toroidformet graf har maksimalt kromatisk tall 7. Den komplette grafen K 7 gir et eksempel på en toroidegraf med kromatisk nummer 7.

Enhver trekantfri toroid graf har maksimalt kromatisk tall 4.

Ved et resultat som er analogt med Fárys teorem , kan en hvilken som helst toroidform graf tegnes med rette kanter i et rektangel med periodiske grenseforhold . Videre gjelder analogen til Tutte vårteori i dette tilfellet. Toroidale grafer har også bokinnbeddinger på maksimalt 7 sider.

Hindringer

Ved Robertson-Seymour teorem , eksisterer det et begrenset sett H av minimale ikke-toroidal-diagrammer, slik at en kurve som er toroidal hvis og bare hvis den har ingen graf mindre i H . Det vil si at H danner settet med forbudte mindreårige for de toroidale grafene. Hele settet H er ikke kjent, men det har minst 17 523 grafer. Alternativt er det minst 250.815 ikke-toroidale grafer som er minimale i den topologiske mindre rekkefølgen. En graf er toroidal hvis og bare hvis den ikke har noen av disse grafene som en topologisk minor.

Galleri

Se også

Merknader

Referanser

  • Chartrand, Gary ; Zhang, Ping (2008), Kromatisk grafteori , CRC Press, ISBN 978-1-58488-800-0.
  • Endo, Toshiki (1997), "Sidetallet på toroidale grafer er maksimalt syv", Diskret matematikk , 175 (1–3): 87–96, doi : 10.1016 / S0012-365X (96) 00144-6 , MR  1475841.
  • Gortler, Steven J .; Gotsman, Craig; Thurston, Dylan (2006), "Discrete one-forms on meshes and applications to 3D mesh parameterization" (PDF) , Computer Aided Geometric Design , 23 (2): 83–112, doi : 10.1016 / j.cagd.2005.05.002 , MR  2189438.
  • Heawood, PJ (1890), "Map coloring theorems", Quarterly Journal of Mathematics , First Series, 24 : 322–339.
  • Kocay, W .; Neilson, D .; Szypowski, R. (2001), "Drawing charts on the torus" (PDF) , Ars Combinatoria , 59 : 259–277, MR  1832459 , arkivert fra originalen (PDF) 2004-12-24 , hentet 2018-09- 06.
  • Kronk, Hudson V .; White, Arthur T. (1972), "A 4-color theorem for toroidal graphs", Proceedings of the American Mathematical Society , American Mathematical Society, 34 (1): 83–86, doi : 10.2307 / 2037902 , JSTOR  2037902 , MR  0291019.
  • Marušič, Dragan ; Pisanski, Tomaž (2000), "Den bemerkelsesverdige generaliserte Petersen grafen G (8,3)" , Matematikk. Slovaca , 50 : 117–121.
  • Myrvold, Wendy ; Woodcock, Jennifer (2018), "Et stort sett med torushindringer og hvordan de ble oppdaget", Electronic Journal of Combinatorics , 25 (1): P1.16, doi : 10.37236 / 3797
  • Neufeld, Eugene; Myrvold, Wendy (1997), "Practical toroidality testing", Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , s. 574–580.
  • Orbanić, Alen; Pisanski, Tomaž ; Randić, Milano ; Servatius, Brigitte (2004), "Blanuša double", Matematikk. Fellesskap. , 9 (1): 91–103.