Hamiltonicidad en torneos multipartitos

Ponente(s): Mika Olsen ., Ana Paulina Figueroa, Juan José Montellano Ballesteros

El estudio de la hamiltonicidad es un tema clásico dentro de la teoría de gráficas y digráficas. Una (di)gráfica es hamiltoniana si contiene un ciclo que pasa exactamente una vez por cada uno de los vértices de la (di)gráfica. Sin embargo, determinar si una (di)gráfica es hamiltoniana es un problema NP-completo, por lo que, generalmente, se estudia en ciertas clases de (di)gráficas o se buscan condiciones suficientes para que una (di)gráfica sea hamiltoniana. Por ejemplo, es sencillo demostrar que todo torneo fuertemente conexo es hamiltoniano, pero en la familia de torneos multipartitos el problema es NP-completo, a pesar de que los torneos multipartitos preservan propiedades y características de los torneos. En esta plática, consideramos una variante del problema de hamiltonicidad: la conexidad por trayectorias hamiltonianas en torneos multipartitos. Determinamos condiciones suficientes para que un torneo multipartito balanceado sea fuertemente conexo por trayectorias hamiltonianas. Estos resultados se obtuvieron al estudiar condiciones suficientes para que un torneo c-partito tuviera una partición en torneos (de orden c) en la cual cada uno de ellos fuera fuertemente conexo por trayectorias hamiltonianas.