The edge reconstruction number of a disconnected graph
Robert Molina · Journal of Graph Theory · 1995
Abstract The edge reconstruction number of a graph G, RN(G), is the minimum number of edge deleted subgraphs required to determine G up to isomorphism. We prove the following results for a disconnected graph G with at least two nontrivial components. If G has a pair of nontrivial nonisomorphic components then RN(G) ≤ 3. If G has a pair of nontrivial nonisomorphic components, is not a forest, and contains a nontrivial component other than K3 or K1,3 then RN(G) ≤ 2. Finally, if all nontrivial components of G are isomorphic to a graph with k edges, then RN(G) ≤ k + 2. The edge reconstruction results in this paper are similar to the vertex reconstruction results stated by Myrvold (“The Ally‐Reconstruction Number of a Disconnected Graph,” Ars Combinatoria, Vol. 28 [1989] pp. 123‐127), but a significant difference is that the edge reconstruction number of a disconnected graph is often two, while the vertex reconstruction number of a graph is always three or more. © 1995 John Wiley & Sons, Inc.