Ciclos Hamiltonianos Alternantes en Multigráficas 2-coloreadas.

Ponente(s): Alejandro Contreras Balbuena, Hortensia Galeana Sánchez, Ilán A. Goldfeder

En una multigráfica 2-coloreada, una trayectoria (respectivamente ciclo) es alternante si cualesquiera dos aristas consecutivas tienen colores distintos. Mas aun, una trayectoria (resp. un ciclo) es Hamiltoniano si contiene a todos los vértices de la gráfica. El problema de determinar la existencia de trayectorias y ciclos Hamiltonianos en multigráficas 2-coloreadas es un problema NP-completo y ha sido estudiado diversos autores. Aunque las condiciones conocidas para la existencia de ciclos Hamiltonianos alternantes resultan ser condiciones globales sobre el número y estructura de las aristas en G (como por ejemplo que sean bipartitas completas, o bipartitas y r-regulares), ambas resultan ser un poco restrictivas sobre la gráfica. Una multigráfica 2-coloreada decimos que es 2-M-cerrada si para cualquier 2-trayectoria monocromática (P=(x,y,z)) existe una arista entre el vértice x y el vértice z. En esta plática caracterizamos a las multigráficas 2-M-cerradas que tienen ciclo Hamiltoniano alternante.