Caracterización de las digráficas núcleo perfectas con un ciclo hamiltoniano como parte asimétrica

Ponente(s): Germán Benítez Bobadilla, Hortensia Galeana Sánchez y César Hernández Cruz.

Un núcleo en una digráfica es un conjunto de vértices que es independiente y absorbente. Sea D una digráfica tal que toda subdigráfica inducida propia tiene un núcleo. Si D tiene núcleo, entonces decimos que D es una digráfica núcleo perfecta (KP-digráfica), de lo contrario decimos que D es una digráfica núcleo imperfecta crítica (CKI-digráfica). En esta charla daremos una caracterización de las KP-dígráficas cuya parte asimétrica es un ciclo hamiltoniano. Además, para las digráficas cuya parte asimétrica es un ciclo hamiltoniano y cuyas diagonales son simétricas con longitud 2, se presenta una construcción que nos permite contraer subtrayectorias del ciclo hamiltoniano, con algunas diagonales, para obtener un dígráfica de menor orden que preserva la existencia, o la no existencia, de un núcleo. De esta forma se obtienen dos algoritmos; el primero determina si una dígráfica es una KP-digráfica o una CKI-digráfica, y el segundo reconstruye el núcleo de la dígráfica original, en caso de ser una KP-digráfica.