Grafico toroidale - Toroidal graph

Image
Un grafico cubico con 14 vertici incorporati su un toro
Image
Il grafico di Heawood e la mappa associata incorporati nel toro.

In matematica , un grafico toroidale è un grafico che può essere incorporato in un toro . In altre parole, i vertici del grafo possono essere posizionati su un toro in modo tale che nessun bordo si intersechi.

Esempi

Qualsiasi grafico che può essere incorporato in un piano può anche essere incorporato in un toro. Un grafo toroidale di genere 1 può essere incorporato in un toro ma non in un piano. Il grafo di Heawood , il grafo completo K 7 (e quindi K 5 e K 6 ), il grafo di Petersen (e quindi il grafo bipartito completo K 3,3 , poiché il grafo di Petersen ne contiene una suddivisione), uno degli snark di Blanuša , e tutte le scale Möbius sono toroidali. Più in generale, qualsiasi grafico con incrocio numero 1 è toroidale. Alcuni grafici con numeri di incrocio maggiori sono anche toroidali: il grafo di Möbius-Kantor , ad esempio, ha numero di incrocio 4 ed è toroidale.

Proprietà

Ogni grafo toroidale ha numero cromatico al massimo 7. Il grafo completo K 7 fornisce un esempio di grafo toroidale con numero cromatico 7.

Qualsiasi grafico toroidale senza triangoli ha un numero cromatico al massimo 4.

Per un risultato analogo al teorema di Fáry , qualsiasi grafo toroidale può essere disegnato con bordi retti in un rettangolo con condizioni al contorno periodiche . Inoltre, in questo caso si applica l'analogo del teorema della molla di Tutte . I grafici toroidali hanno anche incorporamenti di libri con un massimo di 7 pagine.

ostruzioni

Per il teorema di Robertson-Seymour , esiste un insieme finito H di grafi minimi non toroidali, tale che un grafo è toroidale se e solo se non ha grafo minore in H . Cioè, H forma l'insieme dei minori proibiti per i grafici toroidali. L'insieme completo H non è noto, ma ha almeno 17.523 grafici. In alternativa, ci sono almeno 250.815 grafici non toroidali che sono minimi nell'ordinamento topologico minore . Un grafo è toroidale se e solo se non ha nessuno di questi grafici come minore topologico.

Galleria

Guarda anche

Appunti

Riferimenti

  • Chartrand, Gary ; Zhang, Ping (2008), Teoria dei grafi cromatici , CRC Press, ISBN 978-1-58488-800-0.
  • Endo, Toshiki (1997), "Il numero di pagina dei grafici toroidali è al massimo sette", Matematica discreta , 175 (1–3): 87–96, doi : 10.1016/S0012-365X(96)00144-6 , MR  1475841.
  • Gortle, Steven J.; Gotsman, Craig; Thurston, Dylan (2006), "Discrete one-forms on mesh 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), "Teoremi di colorazione delle mappe", Quarterly Journal of Mathematics , prima serie, 24 : 322-339.
  • Kocay, W.; Neilson, D.; Szypowski, R. (2001), "Drawing graphs on the torus" (PDF) , Ars Combinatoria , 59 : 259–277, MR  1832459 , archiviato dall'originale (PDF) il 24-12-2004 , recuperato il 09-2018- 06.
  • Kronk, Hudson V.; White, Arthur T. (1972), "Un teorema a 4 colori per grafici toroidali", 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), "Il notevole grafo di Petersen generalizzato G (8,3)" , Math. Slovacchia , 50 : 117–121.
  • Myrvold, Wendy ; Woodcock, Jennifer (2018), "Una grande serie di ostruzioni toroidali e come sono state scoperte", Electronic Journal of Combinatorics , 25 (1): P1.16, doi : 10.37236/3797
  • Neufeld, Eugenio; Myrvold, Wendy (1997), "Test pratico di toroidalità", Atti dell'ottavo simposio annuale ACM-SIAM sugli algoritmi discreti , pp. 574-580.
  • Orbanic, Alen; Pisanski, Tomaz ; Randic, Milano ; Servatius, Brigitte (2004), "Blanuša double", Math. Comune , 9 (1): 91–103.