Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
This paper investigates the Kelly-Ulam reconstruction problem for point-determining graphs, which are graphs where no two vertices share identical open neighborhoods (twin-free graphs). Determining which structural graph properties are recognizable from vertex-deleted subgraphs is central to understanding the limits of graph isomorphism and subgraph-based neural architectures. The authors prove that the property of being point determining is fully recognizable from the multiset deck of single-vertex deletions.
A graph's status as twin-free—having strictly unique neighborhoods across all vertices—can be definitively identified solely from its collection of single-vertex-deleted cards.
A graph $G$ is point determining, if no two vertices have the same neighborhoods. In this paper, we show that this property is recognizable from the deck of cards of a graph.