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 isomorphism. 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_c$, 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)\ge c+1$ (where $c$ is still the number of vertices in any component), then, again, $G$ can only be copies of $K_c$. 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=t(c)$ such that there exists a disconnected graph with all components of order $c$, isomorphic and not equal to $K_c$, and is such that $rn(G)=t$.