Complexity results in graph reconstruction

We investigate the relative complexity of the graph isomorphism problem (GI) and problems related to the reconstruction of a graph from its vertex-deleted or edge-deleted subgraphs (in particular, deck checking (DC) and legitimate deck (LD) problems). We show that these problems are closely related for all amounts c⩾1c⩾1 of deletion:(1)GI≡isolVDCc, GI≡isolEDCc, GI⩽mlLVDc, and GI≡isopLEDc.(2)For all k⩾2k⩾2, GI≡isopk-VDCc and GI≡isopk-EDCc.(3)For all k⩾2k⩾2, GI⩽mlk-LVDc.(4)GI≡isop2-LVDc.(5)For all k⩾2k⩾2, GI≡isopk-LEDc.For many of these results, even the c=1c=1 case was not previously known.Similar to the definition of reconstruction numbers vrn∃(G)vrn∃(G) [F. Harary, M. Plantholt, The graph reconstruction number, J. Graph Theory 9 (1985) 451–454] and ern∃(G)ern∃(G) (see [J. Lauri, R. Scapellato Topics in Graph Automorphism and Reconstruction, London Mathematical Society, Cambridge University Press, Cambridge, 2003, p. 120]), we introduce two new graph parameters, vrn∀(G)vrn∀(G) and ern∀(G)ern∀(G), and give an example of a family {Gn}n⩾4{Gn}n⩾4 of graphs on nn vertices for which vrn∃(Gn)