La conjetura de Alspach

La conjetura de Alspach es un teorema matemático que caracteriza las coberturas de ciclos disjuntas de grafos completos con longitudes de ciclo prescritas. Recibe su nombre de Brian Alspach , quien la planteó como un problema de investigación en 1981. Darryn Bryant, Daniel Horsley y William Pettersson publicaron una demostración ( 2014 ) . 

En este contexto, una cobertura de ciclos disjuntos es un conjunto de ciclos simples, ninguno de los cuales utiliza la misma arista, que incluyen todas las aristas de un grafo . Para que exista una cobertura de ciclos disjuntos, es necesario que cada vértice tenga grado par , porque el grado de cada vértice es el doble del número de ciclos que incluyen ese vértice, un número par. Y para que los ciclos en una cobertura de ciclos disjuntos tengan una colección dada de longitudes, también es necesario que la suma de las longitudes de los ciclos dadas sea igual al número total de aristas en el grafo dado. Alspach conjeturó que, para grafos completos, estas dos condiciones necesarias también son suficientes: si${\displaystyle n}$es impar (de modo que los grados sean pares) y una lista dada de longitudes de ciclo (todas como máximo)${\displaystyle n}$) añade a${\displaystyle {\tbinom {n}{2}}}$(el número de aristas en el grafo completo) luego el grafo completo${\displaystyle K_{n}}$Siempre se puede descomponer en ciclos de la longitud dada. Esta afirmación fue demostrada por Bryant, Horsley y Pettersson.

Para ver los gráficos completos${\displaystyle K_{n}}$cuyo número${\displaystyle n}$Si el número de vértices es par, Alspach conjeturó que siempre es posible descomponer el grafo en un emparejamiento perfecto y una colección de ciclos de longitudes prescritas que suman${\displaystyle {\tbinom {n}{2}}-{\tfrac {n}{2}}}$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 de los ciclos sea igual al número de aristas que se deben cubrir. Esta variante de la conjetura también fue demostrada por Bryant, Horsley y Pettersson.

El problema de Oberwolfach sobre descomposiciones de grafos completos en copias de un grafo 2- regular dado está relacionado, pero ninguno es un caso especial del otro. Si${\displaystyle G}$es un grafo 2-regular con${\displaystyle n}$vértices, formados a partir de una unión disjunta de ciclos de ciertas longitudes, entonces una solución al problema de Oberwolfach para${\displaystyle G}$También proporcionaría una descomposición del gráfico completo en${\displaystyle (n-1)/2}$copias de cada uno de los ciclos de${\displaystyle G}$. Sin embargo, no todas las descomposiciones de${\displaystyle K_{n}}$En esto, muchos ciclos de cada tamaño pueden agruparse en ciclos disjuntos que forman copias de${\displaystyle G}$y por otro lado no todos los casos de la conjetura de Alspach involucran conjuntos de ciclos que tienen${\displaystyle (n-1)/2}$copias de cada ciclo.

• Alspach, B. (1981), "Problema 3", Problemas de investigación, Matemáticas Discretas , 36 (3): 333, doi : 10.1016/s0012-365x(81)80029-5
• Bryant, Darryn; Horsley, Daniel; Pettersson, William (2014), "Descomposiciones de ciclos V: Grafos completos en ciclos de longitudes arbitrarias", Actas de la Sociedad Matemática de Londres , Tercera Serie, 108 (5): 1153– 1192, arXiv : 1204.3709 , doi : 10.1112/plms/pdt051 , MR 3214677 
• Chartrand, Gary ; Lesniak, Linda; Zhang, Ping (2015), "Conjetura de Alspach" , Gráficos y dígrafos , Libros de texto de matemáticas, vol.  39 (6ª  ed.), CRC Press, pág.  349, ISBN 9781498735803