¿Podemos reconstruir un grafo a partir de sus cartas?

Resumen: ¿Qué información sobre un grafo podemos recuperar si solamente conocemos el conjunto de grafos que obtenemos al eliminar uno de sus vértices? Esta es la pregunta central del problema de reconstrucción de grafos.

 

En la charla introduciremos las nociones de carta y mazo de un grafo, y veremos algunos ejemplos sencillos. A partir de estas ideas definiremos qué significa reconstruir un grafo y qué significa que un grafo sea reconstruible. Presentaremos algunos ejemplos básicos, y enunciaremos la famosa Conjetura de Reconstrucción, que afirma que todo grafo simple y finito con al menos tres vértices es reconstruible.

 

Finalmente, cambiaremos ligeramente la pregunta: en lugar de intentar reconstruir completamente el grafo, nos preguntaremos qué propiedades de un grafo pueden determinarse a partir de su mazo.

 

La charla busca presentar el problema de reconstrucción desde ejemplos elementales, para luego mostrar cómo una pregunta aparentemente sencilla da lugar a una interesante colección de problemas sobre qué información de un grafo sobrevive al borrar cada uno de sus vértices.