On the stronger reconstruction of nearly acyclic graphs

Abstract

A graph is called set-reconstructible if it is determined uniquely (up to isomorphism) by the set of its vertex-deleted subgraphs. The maximal subgraph of a graph \( H \) that is a tree rooted at a vertex \( u \) of \( H \) is the limb at \( u \). It is shown that two families \( \mathcal{F}_1 \) and \( \mathcal{F}_2 \) of nearly acyclic graphs are set-reconstructible. The family \( \mathcal{F}_1 \) consists of all connected cyclic graphs \( G \) with no end vertex such that there is a vertex lying on all the cycles in \( G \) and there is a cycle passing through at least one vertex of every cycle in \( G \). The family \( \mathcal{F}_2 \) consists of all connected cyclic graphs \( H \) with end vertices such that there are exactly two vertices lying on all the cycles in \( H \) and there is a cycle with no limbs at its vertices.