Harary's edge reconstruction conjecture
Harary's edge reconstruction conjecture
Let ) be a finite simple graph with . For each edge of , let denote the maximal subgraph obtained by deleting that edge, and define the edge deck of by
Harary's reconstruction conjecture. If for some graph , then .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.