Nuevos resultados de casihamiltonicidad en generalizaciones de torneos

Ponente(s): Gerardo Miguel Tecpa Galván, Ilán Abraham Goldfeder Ortíz

La existencia de ciclos y trayectorias hamiltonianas en gráficas y digráficas es uno de los temas más recurrentes en la literatura debido a su interés práctico y teórico. A partir del Teorema de Rédei y del teorema de Camion, los cuales garantizan la existencia de trayectorias hamiltonianas y ciclos hamiltonianos en torneos y torneos fuertemente conexos, respectivamente, se han buscado familias de digráficas que generalicen a los torneos y que preserven de alguna manera dichos resultados. Un ejemplo concreto de lo anterior son los torneos multipartitos, los cuales son digráficas en las que hay una partición de sus vértices en conjuntos independientes y cualesquiera dos vértices en partes distintas tienen una única flecha entre ellos. Debido a que en dicha familia no siempre es posible garantizar la existencia de un ciclo hamiltoniano, se introdujo la idea de casihamiltonicidad en digráficas. Dada una digráfica con una partición de sus vértices en conjuntos independientes, un ciclo (trayectoria) es casihamiltoniano (casihamiltoniana) si tiene al menos un vértice en cada una de las partes de la digráfica. En lo que respecta a torneos, es sencillo verificar que toda trayectoria casihamiltoniana es hamiltoniana y viceversa. Más aun, se sabe que todo torneo multipartito tiene una trayectoria casihamiltoniana y si además es fuertemente conexo, entonces tiene un ciclo casihamiltoniano. En esta plática hablaremos sobre condiciones de casihamiltonicidad en torneos multipartitos locales. Dichas digráficas son una generalización de los torneos multipartitos y su comportamiento respecto a la casihamiltonicidad ha permitido extender varios de los resultados sobre hamiltonicidad hacia estas digráficas. Por ejemplo, todo torneo multipartito local tiene una trayectoria casihamiltoniana y, bajo la hipótesis de conexidad fuerte, además es posible garantizar la existencia de un ciclo casihamiltoniano. Además de lo anterior, profundizaremos un poco más y mostraremos condiciones bajo las cuales, dados dos vértices distintos en un torneo multipartito local, es posible encontrar una trayectoria casihamiltoniana que los una.