La conjetura de reconstrucción de Stanisław Ulam es uno de los problemas abiertos más conocidos en la teoría de grafos . Usando la terminología de Frank Harary [1] se puede enunciar de la siguiente manera: Si G y H son dos grafos en al menos tres vértices y ƒ es una biyección de V ( G ) a V ( H ) tal que G \{ v } y H \{ƒ( v )} son isomorfos para todos los vértices v en V ( G ), entonces G y H son isomorfos.
En 1964, Harary [2] extendió la conjetura de reconstrucción a grafos dirigidos en al menos cinco vértices, como la llamada conjetura de reconstrucción de dígrafos. Muchos resultados que apoyaban la conjetura de reconstrucción de dígrafos aparecieron entre 1964 y 1976. Sin embargo, esta conjetura se demostró falsa cuando PK Stockmeyer descubrió varias familias infinitas de pares de contraejemplos de dígrafos (incluidos los torneos) de orden arbitrariamente grande. [3] [4] [5] La falsedad de la conjetura de reconstrucción de dígrafos provocó dudas sobre la conjetura de reconstrucción en sí. Stockmeyer incluso observó que "quizás el considerable esfuerzo que se está dedicando a los intentos de probar la conjetura (de reconstrucción) debería equilibrarse con intentos más serios de construir contraejemplos". [3]
En 1979, Ramachandran revivió la conjetura de reconstrucción de dígrafos en una forma ligeramente más débil llamada la nueva conjetura de reconstrucción de dígrafos . En un dígrafo, el número de arcos incidentes desde (respectivamente, hacia) un vértice v se llama grado de salida ( grado de entrada ) de v y se denota por od ( v ) (respectivamente, id ( v )). La nueva conjetura de dígrafos puede enunciarse de la siguiente manera: [6] [7]
Si D y E son dos dígrafos cualesquiera y ƒ es una biyección de V ( D ) a V ( E ) tal que D \{ v } y E \{ƒ( v )} son isomorfos y ( od ( v ), id ( v )) = ( od ( ƒ ( v )), id ( ƒ ( v ))) para todo v en V ( D ), entonces D y E son isomorfos.
La nueva conjetura de reconstrucción de dígrafos se reduce a la conjetura de reconstrucción en el caso no dirigido, porque si todos los subgrafos de dos grafos con vértices eliminados son isomorfos, entonces los vértices correspondientes deben tener el mismo grado. Por lo tanto, la nueva conjetura de reconstrucción de dígrafos es más fuerte que la conjetura de reconstrucción, pero más débil que la conjetura de reconstrucción de dígrafos refutada. Se ha demostrado que varias familias de dígrafos satisfacen la nueva conjetura de reconstrucción de dígrafos y estas incluyen todos los dígrafos en los pares de contraejemplos conocidos de la conjetura de reconstrucción de dígrafos.
A partir de 2024, no se conoce ningún contraejemplo de la nueva conjetura de reconstrucción de dígrafos. Esta conjetura ahora también se conoce como conjetura de reconstrucción de grado asociado .