The class reconstruction number of maximal planar graphs

Abstract

The reconstruction number rn(G) of a graph G was introduced by Harary and Plantholt as the smallest number of vertex-deleted subgraphs G i = G - vi in the deck of G which do not all appear in the deck of any other graph. For any graph theoretic property P, Harary defined the P- reconstruction number of a graph G ~ P as the smallest number of the G i in the deck of G, which do not all appear in the deck of any other graph in P. We now study the maximal planar graph reconstruction number Mrn(G), proving that its value is either 1 or 2 and characterizing those with value 1.