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 − v i 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 ℳrn(G) , proving that its value is either 1 or 2 and characterizing those with value 1.