The token-reconstruction-family conjecture
Let be a graph, let denote its -token graph, and let a -token reconstruction family of be a family of subsets as defined in the source. Let and be two such reconstruction families, and let denote the automorphism group of . Token-reconstruction-family conjecture. There exists such that
The source presents this as a reformulation of the preceding reconstruction conjecture using a proposition about -token reconstructions. The supplied excerpt does not establish whether this reformulated conjecture has been resolved.
References
- Ruy Fabila-Monroy and Ana Laura Trujillo-Negrete, “Connected (C_4,Diamond)-free Graphs Are Uniquely Reconstructible from Their Token Graphs”, arXiv:2207.12336 (2022).
Progress summary
The reformulated conjecture remains open; known results cover only restricted graph classes or almost all random graphs, not every graph.
The conjecture asserts that any two reconstruction families for the same token graph are related by an automorphism of that token graph. A 2022 paper presents this as a reformulation of the preceding token-reconstruction conjecture, without resolving it.
Known results
- Connected induced--free graphs: reconstruction from is established in the stated range (2022).
- The same paper describes relevant automorphism groups for and , but does not prove the family assertion for arbitrary graphs.
August 2026 almost-every-graph result
Yuanming Luo proves that the ordinary token-graph reconstruction conjecture holds for almost every finite graph, with probability tending to for random graphs. This is related progress, not a proof or counterexample for the token-reconstruction-family conjecture.
Current status (as of November 2026): The token-reconstruction-family conjecture remains open; special graph classes and an almost-every-graph theorem are known, but the exact family-automorphism assertion has no recorded resolution.