Rita Zuazua
Departamento de Matemáticas, Facultad de Ciencias - UNAM

Encontrando y destruyendo ciclos

El Prof. Carsten Thomassen propuso en los 70's los siguientes dos problemas:

- Una digráfica no hamiltoniana es r-hypohamiltoniana si al eliminar cualquier conjunto de r-vértices se vuelve hamiltoniana. ¿Para qué entero positivo r existen digráficas r-hypohamiltonianas?

- ¿Cuál es el número mínimo de vértices que debo eliminar en una gráfica o digráfica para destruir sus ciclos máximos?

En la plática recordaremos los conceptos necesarios y daremos respuestas a estas preguntas.