Vertex Reconstruction Conjecture For Asymmetric Graphs

Consider the following passage from [1]:

As pointed out in [22], graphs which are asymmetric should be easier to reconstruct, yet symmetric graphs (even those which are at least regular), which should present a stiffer challenge, are simple to reconstruct.

From that sentence, I would draw the conclusion that the reconstructibilty of asymmetric graphs was still not known to the authors of that survey in 2006.

While it is possible that further advancements have been made in the intervening years (or that the authors of that article were simply unaware of the result), the fact that none of the usual searches (including synonyms of the term "asymmetric graph" like "rigid" or "trivial automorphism group") turns up anything conclusive on the topic is a little suspicious. Of course, the absence of evidence is not necessarily any proof of absence but in my opinion, such a result would be of such significance (a blockbuster result, one might say) that the article that proved it should be very, very easy to find.

A few more recent sources that appear to omit mention of any result regarding the reconstructibility of asymmetric graphs are [2] and [3].

  1. Asciak, K., et al. "A survey of some open questions in reconstruction numbers." Preprint (2006).

  2. Hartke, Stephen G., et al. "Automorphism groups of a graph and a vertex-deleted subgraph." the electronic journal of combinatorics 17.1 (2010): R134.

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

Tags:

Graph Theory