¿Cada gráfico sin puente tiene un conjunto múltiple de ciclos que cubren cada borde exactamente dos veces?
En matemáticas de teoría de grafos , una doble cobertura de ciclo es una colección de ciclos en un gráfico no dirigido que juntos incluyen cada borde del gráfico exactamente dos veces. Por ejemplo, para cualquier gráfico poliédrico , las caras de un poliedro convexo que representa el gráfico proporcionan una doble cobertura del gráfico: cada arista pertenece exactamente a dos caras.
Es un problema no resuelto, planteado por George Szekeres [1] y Paul Seymour [2] y conocido como la conjetura de la doble cobertura del ciclo , si todo grafo sin puente tiene una doble cobertura del ciclo. La conjetura se puede formular de manera equivalente en términos de incrustaciones de gráficos , y en ese contexto también se conoce como conjetura de incrustación circular .
La formulación habitual de la conjetura de la doble cobertura del ciclo pregunta si cada gráfico no dirigido sin puente tiene una colección de ciclos tal que cada borde del gráfico esté contenido exactamente en dos de los ciclos. El requisito de que el grafo no tenga puentes es una condición necesaria obvia para que exista tal conjunto de ciclos, porque un puente no puede pertenecer a ningún ciclo. Una colección de ciclos que satisfacen la condición de la conjetura de la doble cobertura del ciclo se denomina doble cobertura del ciclo . Algunos gráficos, como los gráficos de ciclos y los gráficos de cactus sin puente , solo se pueden cubrir utilizando el mismo ciclo más de una vez, por lo que este tipo de duplicación está permitida en una cubierta doble de ciclo.
Un snark es un caso especial de un gráfico sin puente, que tiene las propiedades adicionales de que cada vértice tiene exactamente tres aristas incidentes (es decir, el gráfico es cúbico ) y que no es posible dividir los bordes del gráfico en tres coincidencias perfectas ( es decir, el gráfico no tiene coloración de 3 aristas y, según el teorema de Vizing, tiene un índice cromático 4). Resulta que los snarks constituyen el único caso difícil de la conjetura de la doble cobertura del ciclo: si la conjetura es cierta para los snarks, también lo es para cualquier gráfico. [3]
Jaeger (1985) observa que, en cualquier posible contraejemplo mínimo de la conjetura de la doble cobertura del ciclo, todos los vértices deben tener tres o más aristas incidentes. Porque, un vértice con solo un borde incidente forma un puente, mientras que si dos bordes inciden en un vértice, se pueden contraer para formar un gráfico más pequeño de modo que cualquier doble cobertura del gráfico más pequeño se extienda a uno del gráfico original. Por otro lado, si un vértice v tiene cuatro o más aristas incidentes, se pueden “dividir” dos de esas aristas eliminándolas del gráfico y reemplazándolas por una única arista que conecte sus otros dos puntos finales, preservando al mismo tiempo la ausencia de puentes de el gráfico resultante. Nuevamente, una doble cobertura del gráfico resultante se puede extender de manera sencilla a una doble cobertura del gráfico original: cada ciclo del gráfico separado corresponde a un ciclo del gráfico original o a un par de ciclos que se encuentran en v . Por tanto, todo contraejemplo mínimo debe ser cúbico. Pero si un gráfico cúbico puede tener sus aristas de 3 colores (digamos con los colores rojo, azul y verde), entonces el subgrafo de aristas rojas y azules, el subgrafo de aristas azules y verdes, y el subgrafo de aristas rojas y verdes cada uno forma una colección de ciclos disjuntos que juntos cubren todos los bordes del gráfico dos veces. Por lo tanto, cada contraejemplo mínimo debe ser un gráfico cúbico sin puente coloreable de 3 aristas, es decir, un snark. [3]
Un posible ataque al problema de la doble cobertura del ciclo sería demostrar que no puede existir un contraejemplo mínimo, demostrando que cualquier gráfico contiene una configuración reducible , un subgrafo que puede ser reemplazado por un subgrafo más pequeño de una manera que preserve la existencia o inexistencia de doble cubierta de ciclo. Por ejemplo, si un gráfico cúbico contiene un triángulo, una transformación Δ-Y reemplazará el triángulo por un solo vértice; cualquier doble cobertura de ciclo del gráfico más pequeño se puede extender nuevamente a una doble cobertura de ciclo del gráfico cúbico original. Por lo tanto, un contraejemplo mínimo a la conjetura de la doble cobertura del ciclo debe ser un gráfico sin triángulos , descartando algunos snarks como el gráfico de Tietze que contiene triángulos. A través de búsquedas por computadora, se sabe que cada ciclo de longitud 11 o menos en un gráfico cúbico forma una configuración reducible y, por lo tanto, cualquier contraejemplo mínimo de la conjetura de la doble cobertura del ciclo debe tener una circunferencia de al menos 12. [4]
Desafortunadamente, no es posible probar la conjetura de la doble cobertura del ciclo utilizando un conjunto finito de configuraciones reducibles. Cada configuración reducible contiene un ciclo, por lo que para cada conjunto finito S de configuraciones reducibles hay un número γ tal que todas las configuraciones del conjunto contienen un ciclo de longitud como máximo γ. Sin embargo, existen snarks con circunferencia arbitrariamente alta, es decir, con límites arbitrariamente altos en la duración de su ciclo más corto. [5] Un snark G con circunferencia mayor que γ no puede contener ninguna de las configuraciones en el conjunto S , por lo que las reducciones en S no son lo suficientemente fuertes como para descartar la posibilidad de que G pueda ser un contraejemplo mínimo.
Si un gráfico tiene una doble cobertura de ciclo, los ciclos de la cobertura se pueden usar para formar las 2 celdas de un gráfico incrustado en un complejo de celdas bidimensional . En el caso de un gráfico cúbico, este complejo siempre forma una variedad . Se dice que el gráfico está incrustado circularmente en la variedad, ya que cada cara de la incrustación es un ciclo simple en el gráfico. Sin embargo, una doble cobertura de ciclo de un gráfico con un grado mayor que tres puede no corresponder a una incrustación en una variedad: el complejo celular formado por los ciclos de la cubierta puede tener una topología no múltiple en sus vértices. La conjetura de incrustación circular o conjetura de incrustación fuerte [3] establece que todo gráfico biconectado tiene una incrustación circular en una variedad. Si es así, el gráfico también tiene una doble cubierta de ciclo, formada por las caras del incrustamiento.
Para gráficos cúbicos, la biconectividad y la falta de puentes son equivalentes. Por lo tanto, la conjetura de la incrustación circular es claramente al menos tan fuerte como la conjetura de la doble cobertura del ciclo. Sin embargo, resulta que no es más fuerte. Si los vértices de un gráfico G se expanden para formar un gráfico cúbico, que luego se incrusta circularmente, y las expansiones se deshacen contrayendo los bordes agregados, el resultado será una incrustación circular del propio G. Por lo tanto, si la conjetura de la doble cobertura del ciclo es cierta, todo gráfico biconectado tiene una incrustación circular. Es decir, la conjetura de la doble cobertura del ciclo es equivalente a la conjetura de la incrustación circular, aunque una doble cobertura del ciclo y una incrustación circular no siempre son lo mismo. [3]
Si existe una incrustación circular, es posible que no esté en una superficie de género mínimo: Nguyen Huy Xuong describió un gráfico toroidal biconectado ninguna de cuyas incrustaciones circulares se encuentran sobre un toroide. [3]
Una versión más fuerte de la conjetura de incrustación circular que también se ha considerado es la conjetura de que todo gráfico biconectado tiene una incrustación circular en una variedad orientable . En términos de la conjetura de la doble cobertura del ciclo, esto equivale a la conjetura de que existe una doble cobertura del ciclo, y una orientación para cada uno de los ciclos de la cobertura, tal que para cada arista e los dos ciclos que cubren e están orientados en direcciones opuestas a través de e . [3]
Alternativamente, también se han considerado refuerzos de la conjetura que involucran coloraciones de los ciclos en la portada. La más fuerte de ellas es la conjetura de que todo gráfico sin puente tiene una incrustación circular en una variedad orientable en la que las caras pueden tener cinco colores. De ser cierto, esto implicaría una conjetura de WT Tutte de que cada gráfico sin puente tiene un flujo 5 en ninguna parte cero . [3]
Un tipo de incrustación más fuerte que una incrustación circular es una incrustación poliédrica , una incrustación de un gráfico en una superficie de tal manera que cada cara es un ciclo simple y cada dos caras que se cruzan lo hacen en un solo vértice o en un solo borde. . (En el caso de un gráfico cúbico, esto se puede simplificar al requisito de que cada dos caras que se cruzan lo hagan en una sola arista). Por lo tanto, en vista de la reducción de la conjetura de la doble cobertura del ciclo a snarks, es de interés para investigar incrustaciones poliédricas de snarks. Al no poder encontrar tales incrustaciones, Branko Grünbaum conjeturó que no existen, pero Kochol (2009a, 2009b) refutó la conjetura de Grünbaum al encontrar un snark con una incrustación poliédrica.