Reconstruction Numbers for Unicyclic Graphs

Abstract

The \emph{Reconstruction Number} of a graph $G$, denoted $RN(G)$, is the minimum number $k$ such that there exist $k$ vertex-deleted subgraphs of $G$ which determine $G$ up to isomorphism. More precisely, $RN(G)=k$ if and only if there are vertex-deleted subgraphs $G_1,G_2,\dots ,G_k$, such that if $H$ is any graph with vertex-deleted subgraphs $H_1,H_2,\dots ,H_k$, and $G_i\cong H_i$ for $i=1,2,\dots ,k$, then $G\cong H$.

A \emph{unicyclic graph} is a connected graph with exactly one cycle. In this paper, we find reconstruction numbers for various types of unicyclic graphs. With one exception, all unicyclic graphs considered have $RN(G)=3$.