Reconstruction Numbers for Unicyclic Graphs

Robert Molina1
1Alma College

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, \ldots, G_k \), such that if \( H \) is any graph with vertex-deleted subgraphs \( H_1, H_2, \ldots, H_k \), and \( G_i \cong H_i \) for \( i = 1, 2, \ldots, 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 \).