En la teoría de grafos , una descomposición cíclica es una descomposición (una división de los bordes de una gráfica) en ciclos . Cada vértice de un gráfico que tiene una descomposición cíclica debe tener un grado par.
Descomposición cíclica de y
Brian Alspach y Heather Gavlas establecieron las condiciones necesarias y suficientes para la existencia de una descomposición de un gráfico completo de orden par menos un factor 1 (una correspondencia perfecta ) en ciclos pares y un gráfico completo de orden impar en ciclos impares. [1] Su demostración se basa en los gráficos de Cayley , en particular, los gráficos circulantes , y muchas de sus descomposiciones provienen de la acción de una permutación en un subgrafo fijo.
Demostraron que para enteros pares positivos y con , la gráfica (dónde es un factor 1) se puede descomponer en ciclos de longitud si y solo si el número de aristas en es un múltiplo de . Además, para enteros impares positivos y con , la gráfica se puede descomponer en ciclos de duración si y solo si el número de aristas en es un múltiplo de .
Referencias
- ^ Alspach, Brian (2001). "Ciclo de descomposiciones de y ". Journal of Combinatoria Teoría, Series B . 81 :. 77-99 doi : 10.1006 / jctb.2000.1996 .
- Bondy, JA; Murty, USR (2008), "2.4 Descomposiciones y recubrimientos", Teoría de grafos , Springer, ISBN 978-1-84628-969-9.