Conjetura de Alspach
La conjetura de Alspach es un teorema matemático que caracteriza las cubiertas de ciclos disjuntos de gráficos completos con longitudes de ciclo prescritas. Lleva el nombre de Brian Alspach , quien lo planteó como un problema de investigación en 1981. Darryn Bryant, Daniel Horsley y William Pettersson ( 2014 ) publicaron una prueba .
En este contexto, una cobertura de ciclo disjunto es un conjunto de ciclos simples, ninguno de los cuales usa el mismo borde, que incluye todos los bordes de un gráfico. Para que exista una cobertura de ciclo disjunto, es necesario que cada vértice tenga un grado par , porque el grado de cada vértice es dos veces el número de ciclos que incluyen ese vértice, un número par. Y para que los ciclos en una cubierta de ciclo disjunto tengan una colección determinada de longitudes, también es necesario que la suma de las longitudes de ciclo dadas sea igual al número total de aristas en el gráfico dado. Alspach conjeturó que, para gráficos completos, estas dos condiciones necesarias también son suficientes: si es impar (para que los grados sean pares) y una lista dada de longitudes de ciclo (como máximo ) se suma a(el número de aristas en el gráfico completo), entonces el gráfico completo siempre se puede descomponer en ciclos de la longitud dada. Es esta afirmación la que demostraron Bryant, Horsley y Pettersson.
Para gráficos completos cuyo número de vértices es par, Alspach conjeturó que siempre es posible descomponer el gráfico en una coincidencia perfecta y una colección de ciclos de longitudes prescritas que suman . En este caso, el emparejamiento elimina el grado impar en cada vértice, dejando un subgrafo de grado par, y la condición restante es nuevamente que la suma de las longitudes del ciclo es igual al número de aristas a cubrir. Esta variante de la conjetura también fue probada por Bryant, Horsley y Pettersson.
