Gráfico toroidal - Toroidal graph

Image
Un gráfico cúbico con 14 vértices incrustados en un toro.
Image
El gráfico de Heawood y el mapa asociado incrustados en el toro.

En matemáticas , un gráfico toroidal es un gráfico que se puede incrustar en un toro . En otras palabras, los vértices del gráfico se pueden colocar en un toro de modo que no se crucen los bordes.

Ejemplos de

Cualquier gráfico que se pueda incrustar en un plano también se puede incrustar en un toro. Un gráfico toroidal del género 1 se puede incrustar en un toro pero no en un plano. El gráfico de Heawood , el gráfico completo K 7 (y por lo tanto K 5 y K 6 ), el gráfico de Petersen (y por lo tanto el gráfico bipartito completo K 3,3 , ya que el gráfico de Petersen contiene una subdivisión del mismo), uno de los snarks de Blanuša , y todas las escaleras de Möbius son toroidales. De manera más general, cualquier gráfico con cruce número 1 es toroidal. Algunas gráficas con números de cruce mayores también son toroidales: la gráfica de Möbius-Kantor , por ejemplo, tiene el número de cruce 4 y es toroidal.

Propiedades

Cualquier gráfico toroidal tiene un número cromático como máximo 7. El gráfico completo K 7 proporciona un ejemplo de gráfico toroidal con número cromático 7.

Cualquier gráfico toroidal sin triángulos tiene un número cromático como máximo 4.

Mediante un resultado análogo al teorema de Fáry , cualquier gráfico toroidal puede dibujarse con bordes rectos en un rectángulo con condiciones de contorno periódicas . Además, en este caso se aplica el análogo del teorema del resorte de Tutte . Los gráficos toroidales también tienen incrustaciones de libros con un máximo de 7 páginas.

Obstrucciones

Por el teorema de Robertson-Seymour , existe un conjunto finito H de gráficos no toroidales mínimos, de tal manera que un gráfico es toroidal si y sólo si no tiene menor gráfica en H . Es decir, H forma el conjunto de menores prohibidos para los gráficos toroidales. No se conoce el conjunto completo H , pero tiene al menos 17 523 gráficos. Alternativamente, hay al menos 250,815 gráficos no toroidales que son mínimos en el orden topológico menor . Un gráfico es toroidal si y solo si no tiene ninguno de estos gráficos como topológico menor.

Galería

Ver también

Notas

Referencias

  • Chartrand, Gary ; Zhang, Ping (2008), teoría de grafos cromáticos , CRC Press, ISBN 978-1-58488-800-0.
  • Endo, Toshiki (1997), "El número de páginas de gráficos toroidales es como máximo siete", Discrete Mathematics , 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 mesh and applications to 3D mesh parametrización" (PDF) , Computer Aided Geometric Design , 23 (2): 83–112, doi : 10.1016 / j.cagd.2005.05.002 , MR  2189438.
  • Heawood, PJ (1890), "Teoremas de coloración de mapas", Quarterly Journal of Mathematics , Primera serie, 24 : 322–339.
  • Kocay, W .; Neilson, D .; Szypowski, R. (2001), "Drawing graphs on the torus" (PDF) , Ars Combinatoria , 59 : 259–277, MR  1832459 , archivado desde el original (PDF) el 24 de diciembre de 2004 , consultado el 9 de septiembre de 2018 06.
  • Kronk, Hudson V .; White, Arthur T. (1972), "Un teorema de 4 colores para gráficos toroidales", 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), "El notable gráfico de Petersen generalizado G (8,3)" , Math. Eslovaca , 50 : 117–121.
  • Myrvold, Wendy ; Woodcock, Jennifer (2018), "Un gran conjunto de obstrucciones toroidales y cómo se descubrieron", Electronic Journal of Combinatorics , 25 (1): P1.16, doi : 10.37236 / 3797
  • Neufeld, Eugene; Myrvold, Wendy (1997), "Pruebas prácticas de toroidalidad", Actas del octavo simposio anual ACM-SIAM sobre algoritmos discretos , págs. 574–580.
  • Orbanić, Alen; Pisanski, Tomaž ; Randić, Milán ; Servatius, Brigitte (2004), "Blanuša doble", Matemáticas. Comun. , 9 (1): 91–103.