Conjetura de reconstrucción de vértices para grafos asimétricos

Question

¿Se sabe si todos los grafos que tienen un grupo de automorfismo trivial son reconstruibles por vértices? Y si es así, ¿cuál es la prueba?

Answer 1

Consideremos el siguiente pasaje de [1]:

Como se señala en [22], los grafos asimétricos deberían ser más fáciles de reconstruir, pero los simétricos (incluso los que son al menos regulares), que deberían presentar un reto más duro, son sencillos de reconstruir.

De esa frase, yo sacaría la conclusión de que la reconstructibilidad de los gráficos asimétricos todavía no era conocida por los autores de esa encuesta en 2006.

Aunque es posible que se hayan producido nuevos avances en los años transcurridos (o que los autores de ese artículo simplemente no conocieran el resultado), el hecho de que ninguna de las búsquedas habituales (incluyendo sinónimos del término "grafo asimétrico" como "rígido" o "grupo de automorfismo trivial") arroje nada concluyente sobre el tema es un poco sospechoso. Por supuesto, la ausencia de pruebas no es necesariamente una prueba de ausencia, pero en mi opinión, un resultado así sería de tal importancia (un resultado taquillero, podríamos decir) que el artículo que lo demostrara debería ser muy, muy fácil de encontrar.

Algunas fuentes más recientes que parecen omitir la mención de cualquier resultado relativo a la reconstruibilidad de los grafos asimétricos son [2] y [3].

1. Asciak, K., et al. " Un estudio de algunas cuestiones abiertas en los números de reconstrucción. " Preprint (2006).

2. Hartke, Stephen G., et al. " Grupos de automorfismo de un grafo y de un subgrafo con vértices eliminados. " la revista electrónica de combinatoria 17.1 (2010): R134.

3. Lauri, Josef, y Raffaele Scapellato. Topics in graph automorphisms and reconstruction. Cambridge University Press, 2003.

Answer 2

Por un conocido teorema de Erdös, los grafos asimétricos no triviales más pequeños tienen V(G)=6. La conjetura de reconstrucción afirma que todos los grafos finitos con 3 vértices o más son reconstruibles por vértices. Por tanto, la reconstruibilidad de vértices de los grafos asimétricos finitos no triviales depende totalmente de este resultado fundamental, aún no demostrado. La cuestión de si los grafos asimétricos son todos reconstruibles por vértices es esencialmente una iteración de la propia Conjetura de Reconstrucción.