Harary's edge reconstruction conjecture

Let G=(V,E)G=(V,E)) be a finite simple graph with E>4|E|>4. For each edge of GG, let GiG_i denote the maximal subgraph obtained by deleting that edge, and define the edge deck of GG by

Deck(G){Gi}i=1m.\operatorname{Deck}(G)\coloneqq\{G_i\}_{i=1}^m.

Harary's reconstruction conjecture. If Deck(G)=Deck(H)\operatorname{Deck}(G)=\operatorname{Deck}(H) for some graph HH, then GHG\cong H.

This conjecture asserts that every graph with more than four edges is uniquely determined, up to isomorphism, by its maximal edge-deleted subgraphs. The paper proves it for graphs with exactly one cycle and three non-isomorphic subtrees; the general conjecture remains open.

Sources & referencesView supporting material

Primary source

Anthony E. Pizzimenti and Umarkhon Rakhimov, “Reconstructing edge-deleted unicyclic graphs”, arXiv:2411.03133 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.