Edge-Reconstruction of Cartesian Product Graphs

This thesis solves the weak edge-reconstruction problem for Cartesian products. In other words, it is shown that any nontrivial finite or infinite Cartesian product G with edge-set E(G) is uniquely determined up to isomorphisms by any edge-deleted subgraph {G − e|e ∈ E(G)}. For finite Cartesian products the thesis also presents an algorithm for the computation of G from G − e in O(m∆²) time, where m is the size of G and ∆ its maximal degree. It improves the straightforward algorithm for reconstruction of G, which has complexity O(mn²), where n is the order of G. Because ∆ can be much smaller than n, the improvement can be substantial.