Expansión hamiltoniana

La descomposición hamiltoniana de un gráfico dado es una partición de los bordes del gráfico en ciclos hamiltonianos . Las descomposiciones hamiltonianas se han estudiado tanto para grafos no dirigidos como para grafos dirigidos . En el caso de un gráfico no dirigido, la descomposición hamiltoniana se puede describir como una factorización en 2 del gráfico de modo que cada factor esté conectado. Para que exista tal descomposición para un gráfico no dirigido, debe ser un gráfico regular conexo con un grado par de . Un gráfico dirigido con tal descomposición debe estar fuertemente conectado y todos los vértices deben tener los mismos grados de entrada y salida, pero estos grados no tienen que ser pares [1] .

Se sabe que cualquier grafo completo con un número impar de vértices tiene una descomposición hamiltoniana. Este resultado, que es un caso especial del problema de Oberwolfach de descomponer gráficos completos en 2 factores isomorfos, fue atribuido por Eduard Luca en 1892 a Walecki. La construcción de Walecki coloca los vértices en un polígono regular y cubre el gráfico completo en este subconjunto de vértices con caminos hamiltonianos en zigzag a través del polígono con cada camino rotado por un ángulo múltiple. Luego, las rutas se pueden completar en ciclos hamiltonianos conectando sus extremos a través del vértice restante [2] .

Los gráficos completos orientados a casos son torneos . Respondiendo a la conjetura de Kelly de 1968, Daniela Kühn y Dirik Oestus demostraron en 2012 que cualquier torneo regular suficientemente grande tiene una descomposición hamiltoniana [3] .

Comprobar si un gráfico arbitrario tiene una descomposición hamiltoniana es un problema NP-completo tanto para gráficos dirigidos como no dirigidos [4] .

Notas

1. ↑ Bermond J.-C. Descomposiciones hamiltonianas de grafos, grafos dirigidos e hipergrafos // Annals of Discrete Mathematics. - 1978. - T. 3 . — P. 21–28 . - doi : 10.1016/S0167-5060(08)70494-1 .
2. ↑ Brian Alspach. La maravillosa construcción Walecki // Boletín del Instituto de Combinatoria y sus Aplicaciones. - 2008. - T. 52 . — Pág. 7–20 .
3. ↑ Daniela Kühn, Deryk Osthus. Descomposiciones de Hamilton de expansores regulares: una prueba de la conjetura de Kelly para grandes torneos // Avances en Matemáticas. - 2013. - T. 237 . — Pág. 62–146 . -doi : 10.1016/ j.aim.2013.01.005 . -arXiv : 1202.6219 . _
4. ↑ Péroche B. NP-completitud de algunos problemas de partición y cobertura en grafos // Matemática Aplicada Discreta. - 1984. - T. 8 , núm. 2 . — S. 195–208 . - doi : 10.1016/0166-218X(84)90101-X .