On certain classes of graphs with large reconstruction number

Abstract

The reconstruction problem is considered to be one of the most important unsolved problems in graph theory. Thus graph theorists have tried to study variants of this problem. One such variant was studied by Harary and Plantholt who came up with the idea of the reconstruction number - the minimum number of vertex-deleted subgraphs required in order to identify a graph up to isomorphism. The edge-reconstruction number of a graph is analogously defined. Myrvold and Molina have shown that disconnected graphs with at least two non-isomorphic components have reconstruction number equal to 3 and edge-reconstruction number equal to 2.