Rigidity and reconstruction for graphs

Abstract

The edge reconstruction conjecture of Harary (1964) states that a finite graph $G$ can be reconstructed up to isomorphism from the multiset of its edge-deleted subgraphs $G–e$ (with $e$ running over the edges of $G$). We put this conjecture in the framework of measure-theoretic rigidity, revealing the importance of the lengths of labeled closed walks for the problem.