En las matemáticas de teoría de grafos , una doble cobertura de ciclos es una colección de ciclos en un grafo no dirigido que juntos incluyen cada arista del grafo exactamente dos veces. Por ejemplo, para cualquier grafo poliédrico , las caras de un poliedro convexo que representa el grafo proporcionan una doble cobertura del grafo: cada arista pertenece exactamente a dos caras.
Se trata de un problema no resuelto , planteado por WT Tutte , [1] Itai y Rodeh, [2] George Szekeres [3] y Paul Seymour [4] y conocido como la conjetura de doble cobertura cíclica , sobre si cada grafo sin puente tiene una doble cobertura cíclica. La conjetura se puede formular de forma equivalente en términos de incrustaciones de grafos , y en ese contexto también se conoce como la conjetura de incrustación circular .
La formulación habitual de la conjetura de doble cobertura de ciclos pregunta si cada grafo no dirigido sin puentes tiene una colección de ciclos tales que cada arista del grafo está contenida en exactamente 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 satisface la condición de la conjetura de doble cobertura de ciclos se denomina doble cobertura de ciclos . Algunos grafos, como los grafos de ciclos y los grafos cactus sin puentes , 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 doble cobertura de ciclos.
Un snark es un caso especial de un grafo sin puente, que tiene las propiedades adicionales de que cada vértice tiene exactamente tres aristas incidentes (es decir, el grafo es cúbico ) y que no es posible dividir las aristas del grafo en tres coincidencias perfectas (es decir, el grafo no tiene coloración de 3 aristas y, por el teorema de Vizing, tiene índice cromático 4). Resulta que los snarks forman el único caso difícil de la conjetura de doble cobertura del ciclo: si la conjetura es verdadera para los snarks, es verdadera para cualquier grafo. [5]
Jaeger (1985) observa que, en cualquier contraejemplo mínimo potencial a la conjetura de doble recubrimiento del ciclo, todos los vértices deben tener tres o más aristas incidentes. En efecto, un vértice con una sola arista incidente forma un puente, mientras que si dos aristas son incidentes en un vértice, se pueden contraer para formar un grafo más pequeño de modo que cualquier doble recubrimiento del grafo más pequeño se extienda a uno de los grafos originales. Por otra parte, si un vértice v tiene cuatro o más aristas incidentes, se pueden “separar” dos de esas aristas quitándolas del grafo y reemplazándolas por una única arista que conecte sus otros dos puntos finales, mientras se preserva la ausencia de puentes del grafo resultante. De nuevo, una doble cobertura del grafo resultante se puede extender de una manera sencilla a una doble cobertura del grafo original: cada ciclo del grafo separado corresponde a un ciclo del grafo 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 grafo cúbico puede tener sus aristas coloreadas en 3 colores (por ejemplo, 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 forman cada uno una colección de ciclos disjuntos que juntos cubren todas las aristas del grafo dos veces. Por lo tanto, cada contraejemplo mínimo debe ser un grafo cúbico sin puentes que no pueda colorearse en 3 aristas, es decir, un snark. [5]
Un posible ataque al problema de la doble cobertura del ciclo sería demostrar que no puede existir un contraejemplo mínimo, probando que cualquier grafo contiene una configuración reducible , un subgrafo que puede ser reemplazado por un subgrafo más pequeño de una manera que preservaría la existencia o no existencia de una doble cobertura del ciclo. Por ejemplo, si un grafo cúbico contiene un triángulo, una transformación Δ-Y reemplazará el triángulo por un solo vértice; cualquier doble cobertura del ciclo del grafo más pequeño puede extenderse de nuevo a una doble cobertura del ciclo del grafo cúbico original. Por lo tanto, un contraejemplo mínimo a la conjetura de la doble cobertura del ciclo debe ser un grafo sin triángulos , descartando algunos snarks como el grafo de Tietze que contienen triángulos. A través de búsquedas por computadora, se sabe que cada ciclo de longitud 11 o menos en un grafo cúbico forma una configuración reducible y, por lo tanto, que cualquier contraejemplo mínimo a la conjetura de la doble cobertura del ciclo debe tener una circunferencia de al menos 12. [6]
Desafortunadamente, no es posible probar la conjetura de doble cobertura del ciclo usando 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 en el 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 longitud de su ciclo más corto. [7] 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 grafo tiene una doble cubierta de ciclo, los ciclos de la cubierta se pueden usar para formar las 2-celdas de un grafo que se incrusta en un complejo de celdas bidimensional . En el caso de un grafo cúbico, este complejo siempre forma una variedad . Se dice que el grafo está incrustado circularmente en la variedad, en el sentido de que cada cara de la incrustación es un ciclo simple en el grafo. Sin embargo, una doble cubierta de ciclo de un grafo con grado mayor que tres puede no corresponder a una incrustación en una variedad: el complejo de celdas formado por los ciclos de la cubierta puede tener una topología no de variedad en sus vértices. La conjetura de incrustación circular o conjetura de incrustación fuerte [5] establece que cada grafo conexo de 2 vértices tiene una incrustación circular en una variedad. Si es así, el grafo también tiene una doble cubierta de ciclo, formada por las caras de la incrustación.
En el caso de los grafos cúbicos, la conectividad de dos vértices y la ausencia de puentes son equivalentes. Por lo tanto, la conjetura de incrustación circular es claramente al menos tan sólida como la conjetura de doble cobertura cíclica. [5]
Si existe una incrustación circular, podría no estar en una superficie de género mínimo: Nguyen Huy Xuong describió un gráfico toroidal con 2 vértices conectados, ninguna de cuyas incrustaciones circulares se encuentra en un toro. [5]
Una versión más fuerte de la conjetura de incrustación circular que también se ha considerado es la conjetura de que cada grafo conexo de 2 vértices tiene una incrustación circular en una variedad orientable . En términos de la conjetura de doble cobertura de ciclo, esto es equivalente a la conjetura de que existe una doble cobertura de ciclo, y una orientación para cada uno de los ciclos en la cobertura, de modo que para cada arista e los dos ciclos que cubren e están orientados en direcciones opuestas a través de e . [5]
Como alternativa, también se han considerado reforzamientos de la conjetura que implican coloraciones de los ciclos en la cubierta. La más fuerte de ellas es una conjetura de que cada grafo sin puente tiene una incrustación circular en una variedad orientable en la que las caras pueden ser 5-coloreadas. Si fuera cierto, esto implicaría una conjetura de WT Tutte de que cada grafo sin puente tiene un 5-flujo de cero en ninguna parte . [5]
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 intersecan lo hacen en un solo vértice o una sola arista. (En el caso de un gráfico cúbico, esto se puede simplificar a un requisito de que cada dos caras que se intersecan lo hagan en una sola arista). Por lo tanto, en vista de la reducción de la conjetura de doble cobertura del ciclo a snarks, es de interés investigar incrustaciones poliédricas de snarks. Incapaz de 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.
{{citation}}: Mantenimiento CS1: fecha y año ( enlace ).{{citation}}: Mantenimiento CS1: fecha y año ( enlace ).