¿Es hamiltoniano todo poliedro simple bipartito?
La conjetura de Barnette es un problema sin resolver en la teoría de grafos , una rama de las matemáticas , sobre los ciclos hamiltonianos en grafos. Lleva el nombre de David W. Barnette , profesor emérito de la Universidad de California, Davis ; establece que cada grafo poliédrico bipartito con tres aristas por vértice tiene un ciclo hamiltoniano.
Definiciones
Un gráfico plano es un gráfico no dirigido que se puede incrustar en el plano euclidiano sin cruces . Un gráfico plano se llama poliédrico si y solo si está conectado por 3 vértices , es decir, si no existen dos vértices cuya eliminación desconectaría el resto del gráfico. Un gráfico es bipartito si sus vértices se pueden colorear con dos colores diferentes de modo que cada borde tenga un punto final de cada color. Una gráfica es cúbica (o regular 3 ) si cada vértice es el punto final de exactamente tres aristas. Finalmente, una gráfica es hamiltoniana si existe un ciclo que pasa por cada uno de sus vértices exactamente una vez. La conjetura de Barnette establece que cada grafo poliédrico bipartito cúbico es hamiltoniano.
Según el teorema de Steinitz , un gráfico plano representa los bordes y vértices de un poliedro convexo si y solo si es poliédrico. Un poliedro tridimensional tiene un gráfico cúbico si y solo si es un poliedro simple . Y un gráfico plano es bipartito si y solo si, en una incrustación plana del gráfico, todos los ciclos de caras tienen una longitud uniforme. Por lo tanto, la conjetura de Barnette puede expresarse en una forma equivalente: suponga que un poliedro convexo simple tridimensional tiene un número par de aristas en cada una de sus caras. Entonces, según la conjetura, la gráfica del poliedro tiene un ciclo hamiltoniano.
Historia
PG Tait ( 1884 ) conjeturó que todo grafo poliédrico cúbico es hamiltoniano; esto llegó a conocerse como la conjetura de Tait . Fue refutado por WT Tutte ( 1946 ), quien construyó un contraejemplo con 46 vértices; otros investigadores encontraron más tarde contraejemplos aún más pequeños. Sin embargo, ninguno de estos contraejemplos conocidos es bipartito. El propio Tutte conjeturó que cada grafo bipartito cúbico de 3 conexiones es hamiltoniano, pero se demostró que esto es falso por el descubrimiento de un contraejemplo, el grafo de Horton . [1] David W. Barnette ( 1969 ) propuso una combinación debilitada de las conjeturas de Tait y Tutte, afirmando que todo poliedro cúbico bipartito es hamiltoniano o, de forma equivalente, que todo contraejemplo de la conjetura de Tait no es bipartito.
Formas equivalentes
Kelmans (1994) [2] mostraron que la conjetura de Barnette es equivalente a una declaración superficialmente más fuerte, que por cada dos bordes e y f en la misma cara de un poliedro cúbico bipartito, existe un ciclo de Hamilton que contiene e pero que no contiene f . Es evidente que si esta afirmación es cierta, entonces cada poliedro cúbico bipartita contiene un ciclo de Hamilton: simplemente selecciona e y f arbitrariamente. En las otras direcciones, Kelmans mostró que un contraejemplo podría transformarse en un contraejemplo de la conjetura original de Barnette.
La conjetura de Barnette también es equivalente a la afirmación de que los vértices del dual de cada grafo poliédrico bipartito cúbico se pueden dividir en dos subconjuntos cuyos subgrafos inducidos son árboles. El corte inducido por tal partición en el gráfico dual corresponde a un ciclo hamiltoniano en el gráfico primario. [3]
Resultados parciales
Aunque la verdad de la conjetura de Barnette sigue siendo desconocida, los experimentos computacionales han demostrado que no existe un contraejemplo con menos de 86 vértices. [4]
Si la conjetura de Barnette resulta ser falsa, entonces se puede demostrar que es NP-completo para probar si un poliedro cúbico bipartito es hamiltoniano. [5] Si un gráfico plano es bipartito y cúbico pero solo de conectividad 2, entonces puede ser no hamiltoniano y es NP-completo para probar la hamiltonicidad de estos gráficos. [6] Otro resultado fue obtenido por Alt et al. (2016) : si el gráfico dual puede tener un vértice de color con colores azul, rojo y verde de modo que cada ciclo rojo-verde contenga un vértice de grado 4, entonces el gráfico principal es hamiltoniano.
Problemas relacionados
Una conjetura relacionada de Barnette establece que cada grafo poliédrico cúbico en el que todas las caras tienen seis aristas o menos es hamiltoniano. Los experimentos computacionales han demostrado que, si existe un contraejemplo, debería tener más de 177 vértices. [7] La conjetura fue probada por Kardoš (2020) .
La intersección de estas dos conjeturas sería que cada grafo poliédrico cúbico bipartito en el que todas las caras tienen cuatro o seis aristas es hamiltoniano. Goodey (1975) demostró que esto era cierto .
Notas
- ^ Tutte (1971) ; Horton (1982) .
- ^ Ver Alt et al. (2016) para pruebas
- ^ Florek (2010) .
- ^ Holton, Manvel y McKay (1985) ; Hertel (2005) .
- ^ Feder y Subi (2006) .
- ^ Akiyama, Nishizeki y Saito (1980) .
- ^ Aldred y col. (2000) .
Referencias
- Akiyama, Takanori; Nishizeki, Takao ; Saito, Nobuji (1980), "NP-completitud del problema del ciclo hamiltoniano para gráficos bipartitos" , Journal of Information Processing , 3 (2): 73–76, MR 0596313
- Alt, Helmut; Payne, Michael S .; Schmidt, Jens M .; Wood, David R. (2016), "Reflexiones sobre la conjetura de Barnette" (PDF) , Australasian Journal of Combinatorics , 64 (2): 354–365, MR 3442496
- Aldred, REL; Bau, S .; Holton, DA; McKay, Brendan D. (2000), "Gráficas planas cúbicas conectadas de 3 no hailtonianas", SIAM Journal on Discrete Mathematics , 13 (1): 25–32, doi : 10.1137 / S0895480198348665 , MR 1737931
- Barnette, David W. (1969), "Conjecture 5", en Tutte, WT (ed.), Recent Progress in Combinatorics: Proceedings of the Third Waterloo Conference on Combinatorics, mayo de 1968 , Nueva York: Academic Press, MR 0250896
- Feder, Tomas; Subi, Carlos (2006), Sobre la conjetura de Barnette , ECCC TR06-015
- Florek, Jan (2010), "Sobre la conjetura de Barnette", Discrete Mathematics , 310 (10-11): 1531-1535, doi : 10.1016 / j.disc.2010.01.018 , MR 2601261
- Goodey, PR (1975), "Circuitos hamiltonianos en politopos con caras pares", Israel Journal of Mathematics , 22 (1): 52–56, doi : 10.1007 / BF02757273 , MR 0410565
- Hertel, Alexander (2005), Una encuesta y fortalecimiento de la conjetura de Barnette (PDF)
- Holton, DA; Manvel, B .; McKay, BD (1985), "Ciclos hamiltonianos en grafos planos bipartitos cúbicos conectados en 3", Journal of Combinatorial Theory , Serie B , 38 (3): 279-297, doi : 10.1016 / 0095-8956 (85) 90072-3 , MR 0796604
- Horton, JD (1982), "Sobre dos factores de gráficas regulares bipartitas", Matemáticas discretas , 41 (1): 35–41, doi : 10.1016 / 0012-365X (82) 90079-6 , MR 0676860
- Kardoš, F. (2020), "Una prueba asistida por computadora de la conjetura de Barnette-Goodey: no solo los gráficos fullerenos son hamiltonianos", SIAM Journal on Discrete Mathematics , 34 (1): 62–100, arXiv : 1409.2440 , doi : 10.1137 / 140984737
- Kelmans, AK (1994), "Construcciones de grafos cúbicos bipartitos de 3 conexiones sin ciclos hamiltonianos", en Kelmans, AK (ed.), Temas seleccionados en matemáticas discretas: Actas del Seminario de matemáticas discretas de Moscú 1972-1990 , Sociedad matemática estadounidense Traducciones, Serie 2, 158 , págs. 127–140
- Tait, PG (1884), "Listing's Topologie ", Philosophical Magazine , quinta serie, 17 : 30–46; Reimpreso en Scientific Papers , vol. II, págs. 85–98
- Tutte, WT (1946), "On hamiltonian circuits", Journal of the London Mathematical Society , 21 (2): 98–101, doi : 10.1112 / jlms / s1-21.2.98
- Tutte, WT (1971), "Sobre los 2 factores de las gráficas bicúbicas", Matemáticas discretas , 1 (2): 203-208, doi : 10.1016 / 0012-365X (71) 90027-6 , MR 0291010
enlaces externos
- Weisstein, Eric W. , "Conjetura de Barnette" , MathWorld
- La conjetura de Barnette en el jardín de problemas abiertos, Robert Samal, 2007.