of spanning trees in $G$, the number of Hamiltonian cycles in $G$ etc., can be computed from $\mathcal{N}(G)$. In the standard proof of the reconstructibility of these invariants, one first counts the disconnected subgraphs of each type, (see [@bondy1991]). In view of Theorem \[thm-equiv-disc\], the proofs in Section \[sec-nmatrix\] are more involved. Theorem \[thm-equiv-disc\] implies that if there are counter examples to Ulam’s conjecture then there are many more counter examples to reconstruction from the $\mathcal{N}$-matrix. Therefore, we hope that the study of $\mathcal{N}$-matrix reconstructibility will highlight new difficulties. Similar generalisations of the reconstruction problem were also suggested by Tutte, (notes on pp. 123-124 in [@tutte1984]).

Reconstruction of the characteristic polynomial
-----------------------------------------------

The proof of the reconstructibility of the characteristic polynomial of a graph from its $\mathcal{N}$-matrix is also of independent technical interest, since other authors have considered the question of computing $P(G; \lambda)$ given the [*polynomial deck*]{} $\{P(G-u;\lambda); u \in VG\}$. This question was originally proposed by Gutman and Cvetkovic [@gut-cve1975], and has been studied by others, for example, [@schwenk1979] & [@sciriha2002]. This question remains open. So we consider a weaker question in Section \[sec-poly\]: the question of computing the characteristic polynomial of a graph from its complete polynomial 