reconstruction conjecture
Statement
All graphs below are finite, simple and undirected.
For a graph , a vertex-deleted subgraph of is a subgraph obtained by deleting exactly one vertex together with all edges incident to it; it is an induced subgraph of . The deck of is the multiset
where denotes the isomorphism class of ; the members of are called cards. Two graphs and are hypomorphic if as multisets.
An edge-deleted subgraph of is a subgraph obtained by deleting exactly one edge (keeping all vertices), and the edge-deck of is the multiset
(1) Reconstruction. For every pair of graphs and with , if then .
(2) Set reconstruction. For every pair of graphs and with , if the sets of isomorphism classes of vertex-deleted subgraphs of and of coincide, that is, if and have the same underlying set, then .
(3) Edge reconstruction. For every pair of graphs and with at least four edges, if then .
Record
- Added
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.