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.