Hamilton-cycle reconstruction conjecture from induced subgraphs

At least 9 years old · documented by

For a graph GG, let [?][?] denote the multiset of its induced subgraphs on [?][?] vertices. There are constants 0≤c<10\leq c<1 and n0≥0n_0\geq 0 such that, for every integer n≥n0n\geq n_0, the number of Hamilton cycles of every nn-vertex graph GG is uniquely determined by the multiset of induced subgraphs of GG on ⌊cn⌋\lfloor cn\rfloor vertices.

Hamilton-cycle reconstruction conjecture. There are constants 0≤c<10\leq c<1 and n0≥0n_0\geq 0 such that, for all integers n≥n0n\geq n_0, the number of Hamilton cycles of an nn-vertex graph GG is uniquely determined from C(G,⌊cn⌋)\mathcal{C}(G,\lfloor cn\rfloor).

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

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.