La conjetura de reconstrucción de grafos afirma que cualquier grafo simple con 3 o más vértices es reconstruible a partir de su "baraja" de subgrafos con vértices eliminados. (Una buena introducción a este problema se encuentra en esta página de Wikipedia .)
Mi pregunta general: Me interesaría cualquier avances recientes en la conjetura. Las fuentes del artículo de Wikipedia parecen bastante antiguas. (También tengo una copia de un Encuesta Bondy y Hemminger de 1977. Un artículo más reciente de Ramachandran (en pdf aquí) es de 2004 pero, como muchos trabajos sobre esta conjetura, se desvía rápidamente hacia otras cuestiones de reconstrucción, reconstrucción de bordes, etc.)
Una pregunta más concreta: dado que se puede reconstruir la secuencia de grados de un grafo, entonces se puede reconstruir cualquier grafo regular. Pero los grafos con exactamente dos grados, $k$ y $k-1$ parecen bastante difíciles de reconstruir. Yo sería especialmente interesado en resultados relacionados con grafos con exactamente dos grados, $k$ y $k-1.$
Más concretamente, ¿podemos reconstruir grafos en los que todos los vértices tengan grado 2 o 3? (Al parecer, Kocay trabajó en ello a principios de los 80, dice Ramachandran.) Seguramente los grafos "pequeños" de grados {2,3} son accesibles a los ordenadores modernos, por lo que ahora puede haber un lugar para la exploración fértil de este problema.
