On disconnected graph with large reconstruction number

Abstract

The reconstruction number rn(G) of graph G is the minimum number of vertex-deleted subgraphs of G required in order to identify G up to isomporphism. Myrvold and Molina have shown that if G is disconnected and not all components are isomorphic then rn(G) = 3, whereas, if all components are isomorphic and have c vertices each, then rn(G) can be as large as c + 2. In this paper we propose and initiate the study of the gap between rn(G) = 3 and rn(G) = c + 2. Myrvold showed that if G consists of p copies of K" then rn(G) = c + 2. We show that, in fact, this is the only class of disconnected graphs with this value of rn(G). We also show that if rn(G) > c + 1 (where c is still the number of vertices in any component), then, again, G can only be copies of Kc. It then follows that there exist no disconnected graphs G with c vertices in each component and rn( G) = c + 1. This poses the problem of obtaining for a given c, the largest value of/ = t(c) such that there exists a disconnected graph with all components of order c, isomorphic and not equal to Kc and is snch that rn(G) = t.