The reconstruction conjecture for finite simple graphs and associated directed graphs (Q2138987)

The author investigates certain directed graphs associated with the famous ``reconstruction conjecture'' by \textit{P. J. Kelly} [On isomorphic transformations. University of Wisconsin (PhD Thesis) (1942)] and \textit{S. Ulam} [A collection of mathematical problems. New York and London: Interscience Publishers (1960; Zbl 0086.24101)]. The reconstruction conjecture states that for any graph \(G\) on at least three vertices, the multiset of ``vertex-deleted'' subgraphs \(\{G - v : v \in V(G)\}\) is unique. An equivalent way of stating the conjecture, which is more technical but relevant to the contents of the paper, is as follows. Given a graph \(G\), say that a graph \(G^\prime\) satisfies property \((\ast)\) if there exists a bijective map \(f: V(G) \rightarrow V(G^\prime)\) such that for any \(v \in V(G)\), there exists a graph isomorphism \(\phi_v: G - v \rightarrow G^\prime - f(v)\). A graph \(G\) is said to be reconstructible if any graph \(G^\prime\) with property \((\ast)\) is isomorphic to \(G\). Then the conjecture states that every graph on at least three vertices is reconstructible. Consider two graphs \(G\), \(G^\prime\), such that \(G^\prime\) satisfies property \((\ast)\), with a bijective map \(f\) and graph isomorphisms \(\{ \phi_v : v \in V(G) \}\). Then, the associated directed graph \(\tilde{G}\) is defined as follows. The vertex set of \(\tilde{G}\) is \(V(G)\). It has two types of directed arrows: normal-arrows and dashed-arrows. There exists a normal-arrow from \(v_1\) to \(v_2\) if and only if \(v_1v_2\) is not an edge in \(G\), but \(f(v_1) \phi_{v_1}(v_2)\) is an edge in \(G^\prime\). There exists a dashed-arrow from \(v_1\) to \(v_2\) if and only if \(f(v_1)f(v_2)\) is not an edge in \(G^\prime\) and \(v_1 \phi^{-1}_{v_1}(f(v_2))\) is an edge in \(G\). The author investigates cases in which reconstructibility can be inferred solely from properties of this associated directed graph. For instance, it is shown that if some vertex in \(\tilde{G}\) has no normal arrows or dashed arrows arising from it, then \(G\) is isomorphic to \(G'\). Finally, many other structural properties from these associated directed graphs are given, for instance, the existence and structure of cycles with alternating normal and dashed arrows.