Hamilton-cycle reconstruction conjecture from induced subgraphs
For a graph , let denote the multiset of its induced subgraphs on vertices. There are constants and such that, for every integer , the number of Hamilton cycles of every -vertex graph is uniquely determined by the multiset of induced subgraphs of on vertices.
Hamilton-cycle reconstruction conjecture. There are constants and such that, for all integers , the number of Hamilton cycles of an -vertex graph is uniquely determined from .
The conjecture proposes that Hamilton-cycle counts, despite involving connected spanning structures, can be reconstructed from induced subgraphs of a fixed linear-size fraction strictly smaller than the full graph. The supplied text gives no resolution, so the conjecture is treated as open.
References
Primary source
Donggyu Kim and Hyunwoo Lee, “Reconstructing hypergraph matching polynomials”, arXiv:2501.19081 (2025).
Additional references
4 papers in this index state this conjecture (2016–2025). The statement above is taken from the most recent of them; the others are arXiv:1804.07104, arXiv:1610.00117, arXiv:1609.09550.
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
No solutions have been posted yet.