Wilfried Imrich: Weak reconstruction of edge-deleted Cartesian products
Abstract. In 1960 Ulam asked whether a graph G is uniquely determined up to isomorphisms by its deck, that is, by the set of all graphs G\x obtained from G by deleting a vertex x and all edges incident to it. This led to the Reconstruction Conjecture, also known as Ulam's Conjecture, that any two graphs on at least three vertices with the same deck are isomorphic. This still is open for finite graphs. When reconstructing a class of graphs, the problem partitions into the subproblems recognition and weak reconstruction. The first consists of showing that membership in the class is determined by the deck, and the latter that nonisomorphic members of the class have different decks.
Imrich and Žerovnik, who showed that both the recognition and the weak reconstruction problem can be solved from a single vertex-deleted subgraph for nontrivial, connected finite or infinite Cartesian products.
In 1964 Harary introduced the Edge Reconstruction Conjecture, that any two graphs with at least four edges that have the same deck of edge-deleted subgraphs are isomorphic. For products this was taken up by Dorfler, who showed that all nontrivial strong products and certain lexicographic products can be reconstructed from the deck of all edge-deleted subgraphs. He did not treat the edge-reconstruction of Cartesian products.
Here we show that both the recognition problem and the weak edge reconstruction problem can be solved from a single edge-deleted subgraph for nontrivial, connected finite or infinite Cartesian products. For finite graphs G the reconstruction is possible in O(mn^2) time, where n is the order and m the size of G.