Sesión Matemática Discreta

Diciembre 15, 12:00 ~ 12:20

El Problema de Hamilton-Waterloo con ciclos pares e impares

PASTINE, Adrián Gabriel

Dados dos 2-factores $F_1$ y $F_2$ con $n$ vertices, el problema de Hamilton-Waterloo estudia si el grafo completo $K_n$ se puede descomponer en copias isomorfas de $F_1$ y $F_2$ (junto con un $1$-factor si $n$ es par). En este trabajo estudiamos el problema cuando $F_1$ consta de ciclos de tama\~{n}o $2^{k_1}x$ y $F_2$ ciclos de tama\~{n}o $2^{k_2}y$, con $n=4^kz$, $0\leq k_1,k_2\leq k$, $x$ e $y$ divisores de $z$. Demostramos que el grafo $K_n$ se puede descomponer en $r$ copias de $F_1$ y $s$ copias de $F_2$ siempre y cuando $1\not\in\{r,s\}$, $r+s=(n-2)/2$. La descomposición que presentaremos hace uso de Grafos de Cayley sobre anillos de polinomios.

Autores: PASTINE, Adrián Gabriel / Keranen, Melissa S..