PreprintCC BY 4.0arXiv
Almost Every Graph Is Reconstructible from Its Token Graphs
Abstract
Let Fk(G) denote the k-token graph of a finite graph G. The token graph reconstruction conjecture asks whether, for any 1≤ k<|V(G)|, Fk(G)≅ Fk(H) implies G≅ H. This paper proves that the conjecture holds for almost every graph.
Related
- The domination number of the $2$-token graph of path graphs
- ALMOST EVERY PAIR OF INTERVAL EXCHANGE TRANSFORMATIONS DOES NOT GENERATE A FREE GROUP
- Every commutative perfect ring is a quotient of an almost perfect domain
- Almost every Boolean function has central threshold degree
- The domination number of the 2-token graph of the complete bipartite graph
BibTeX
@misc{luo2026almost,
title = {{Almost Every Graph Is Reconstructible from Its Token Graphs}},
author = {Yuanming Luo},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.22094},
eprint = {2608.22094},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.22094},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Almost Every Graph Is Reconstructible from Its Token Graphs
AU - Yuanming Luo
PY - 2026
DA - 2026/08/30
PB - arXiv
DO - 10.48550/arxiv.2608.22094
UR - https://arxiv.org/abs/2608.22094
AB - Let F_k(G) denote the k-token graph of a finite graph G. The token graph reconstruction conjecture asks whether, for any 1≤ k<|V(G)|, F_k(G)≅ F_k(H) implies G≅ H. This paper proves that the conjecture holds for almost every graph.
ER -