On the weak reconstruction of Cartesian-product graphs (Q1916107)

The authors prove the startling result that a non-trivial connected Cartesian-product graph (finite or infinite) can be reconstructed from a single vertex-deleted subgraph. While the membership recognition problem is addressed through the algorithm developed in [\textit{J. Feigenbaum}, \textit{J. Herschberger} and \textit{A. A. Schäffer}, A polynomial time algorithm for finding the prime factors of Cartesian-product graphs, Discrete Appl. Math. 12, 123-138 (1985; Zbl 0579.68028)], the weak reconstruction problem is settled here by proving the following: If \(H\) is an arbitrary finite or infinite connected graph and if \(G_1=H\cup x\cup E_x\) and \(G_2=H\cup y\cup E_y\) are one vertex extensions of \(H\), where \(E_x=\{\{x,z\}\mid \{x,z\}\in E(G_1)\}\) and \(E_y=\{\{y,z\}\mid \{y,z\}\in E(G_2)\}\), then \(G_1\) and \(G_2\) are isomorphic, provided they are Cartesian-product graphs.