Reconstruction from one labelled card and more

Abstract

The deck D of a graph H is its multiset of one-vertex deleted subgraphs. Ulam's Reconstruction Conjecture claims that every graph having more than two vertices is reconstructible from D. We seek minimal graph parameters that need to accompany one card G to enable the unique reconstruction of H. A card needs to be feasible. We consider specific graph invariants associated with the 0–1 eigenspaces of H, which need to supplement a feasible card, for the unique reconstruction of H. Non–isomorphic graphs sharing a common card turn out to have linearly independent one-dimensional eigenspaces, whereas non–isomorphic graphs, sharing a common eigenspace, have no labelled card in common. Moreover, we determine certain families of graphs for which reconstruction is possible from any card.