On the edge-reconstruction number of disconnected graphs

Abstract

The edge-reconstruction number of a graph G is the minimum number of edge-deleted subgraphs which are required to determine the isomorphism type of G. Molina has shown that a disconnected graph whose components are not all isomorphic has edge-reconstruction number at most three. He also showed that under certain conditions, including the property that at least one component has a cycle, the edge-reconstruction number is 2. In this paper we give an alter-native proof of Molina’s main result, characterise those disconnected graphs which have the largest possible edge-reconstruction number, and we also investigate what properties can force a forest to have edge-reconstruction number 2.