A new class of reconstructible graphs from some neighbourhood conditions (Q2634755)

Let \(\Gamma =(V,E)\) be a finite simple graph. The graph \(\Gamma =(V,E)\) is called reconstructible iff, for any graph \(\Gamma '=(V',E')\), so that there is a bijective function \(\Phi :V\to V'\) so that, for all \(v\in V\), the graph \(\Gamma -v\) is isomorphic to \(\Gamma '- \Phi (v) \), we have that \(\Gamma '\) is isomorphic to \(\Gamma \). For any \(v\in V\), let \(N(v)\) be the induced subgraph on the set of vertices \(\{ w\in V: [v,w]\in E\} \), let \(St(v)\) be the induced subgraph on the set of vertices \(\{ w\in V: [v,w]\in E\} \cup \{ v\} \). The paper proves that, if a graph \(\Gamma =(V,E)\) satisfies the following two conditions: (1) For any two distinct vertices \(w,w'\in V\), \([w,w']\in E\) is equivalent to \(N(w)-w'\) not being isomorphic to any \(N(s)\) for any \(s\in V\), (2) There exists a vertex \(v\in V\) of degree \(k\), so that, for any \(k\) vertices \(v_1 , \ldots , v_k \in V-v\), there is a vertex \(u\in V\) so that \(St^2 (u)\cap \{ v,v_1 , \ldots , v_k \} =\emptyset \), then \(\Gamma \) is reconstructible. The result and its proof are correct, but needlessly complicated. Remark 3.6 in [\textit{B. S. W. Schröder}, Order 17, No. 3, 255--269 (2000; Zbl 1001.06005)] states that, for any graph with at least 3 vertices, the isomorphism types of all subgraphs \(N(v)\) are reconstructible. (The argument is a simple modification of the proof of the corresponding result for ordered sets, which is Theorem 3.5 there.) Therefore, the following weaker condition: {\parindent=7mm \begin{itemize}\item[(A)] There is a vertex \(w'\in V\) so that, for all \(w\) with \([w,w']\in E\), we have that \(N(w)-w'\) is not isomorphic to any \(N(s)\) for any \(s\in V\). \end{itemize}} is already sufficient for reconstructibility (we use the common approach of reconstructing the graph from the ``deck'' of unlabeled one-vertex-deleted subgraphs). Indeed, it is well known that, for any unlabeled subgraph \(\Gamma -v\), the degree \(\deg(v)\) of \(v\) can be identified. Thus an unlabeled subgraph obtained by removal of a vertex as in condition (A) can be identified as an unlabeled subgraph \(\Gamma -w'\) that has \(\deg(w')\) vertices \(w\) so that \(N(w)-w'\) (which is the neighborhood of \(w\) in \(\Gamma -w'\)) is not isomorphic to any neighborhood graphs \(N(v)\) of \(\Gamma \). Now \(\Gamma \) must be isomorphic to the graph obtained from \(\Gamma -w'\) by attaching a new vertex that is adjacent to exactly these vertices \(w\) of \(\Gamma-w'\). The authors also give a sequence of examples in which the main theorem is used and which, in light of the stronger reconstruction result presented in this review, can be proved much more easily. Moreover, if this reviewer understands the examples correctly, their reconstructibility also follows from the well-known fact that every graph with a disconnected complement is reconstructible.