Reconstructing edge-deleted unicyclic graphs

Abstract

The Harary reconstruction conjecture states that any graph with more than four edges can be uniquely reconstructed from its set of maximal edge-deleted subgraphs. In 1977, Müller verified the conjecture for graphs with $n$ vertices and $n{\log }_2(n)$ edges, improving on Lovás's bound of $\log (n^2-n)/4$. Here, we show that the reconstruction conjecture holds for graphs which have exactly one cycle and and three non-isomorphic subtrees.