Núcleos en digráficas de fichas

Ponente(s): Maria Teresa Idskjen Hoekstra Mendoza, Cesar Hernandez Cruz

El problema de decidir si una digráfica tiene núcleo o no es un problema NP completo. La digráfica de $k$-fichas de una digráfica $G$ es la digráfica $F_k(G)$ es la digráfica que se obtiene al mover $k$ fichas de sobre $G$ de una en una sin que choquen las fichas entre sí. Se sabe que una digráfica sin ciclos dirigidos de longitud impar, tiene núcleo. También es bien conocido que si $G$ no tiene ciclos de longitud impar, entonces $F_k(G)$ tampoco los tiene. La pregunta natural que surge es ¿Si una digráfica tiene núcleo, será cierto que su digráfica de fichas también tiene núcleo? Resulta que existen digráficas que tienen núcleo pero sus digráficas de fichas no tienen y viceversa; existen digráficas que no tienen núcleo pero sus digráficas de fichas si tienen núcleo. En esta plática analizaré un poco este fenómeno y daré algunos resultados en general sobre los núcleos en las digráficas de fichas.