Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 2 min ago
PreprintCC BY 4.0arXiv

Reconstruction and Symmetry of Two-Token Graphs

  • Yuanming Luo
  • Hao Hu
Open at sourcePDFDOICite

Abstract

We present a proof of the two-token graph reconstruction conjecture. Every finite simple graph G,H of order at least three, F2(G) ≅ F2(H) if and only if G ≅ H. We also classify the automorphism groups of two-token graphs whose connected roots have order at least five. Combining these results, we show that, for connected graphs G,H of order at least five, every isomorphism ϕ:F2(G)→ F2(H) admits a factorization ϕ=η∘σ(2), where σ(2) is induced by a graph isomorphism σ:G→ H, and η∈ Aut(F2(H)) is a product of twin-cut switches or Cartesian exchanges.

Related

  1. Almost Every Graph Is Reconstructible from Its Token Graphs
    Yuanming Luo
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. On the Spectra of Generalized Token Graphs of Stars
    Cristina Dalfó, Miquel Àngel Fiol, Berenice Martínez-Barona +1
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. The domination number of the $2$-token graph of path graphs
    Emmanuel Acosta Troncoso, Luis Manuel Rivera
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. On generalized token graphs with tokens of different colors
    Cristina Dalfó, Blas Fernández, Miquel Àngel Fiol +1
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. On generalized k-token graphs with distinguishable tokens and a maximum capacity of s tokens per vertex
    Yiting Cai, Cristina Dalfó, Blas Fernández +1
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{luo2026reconstruction,
  title = {{Reconstruction and Symmetry of Two-Token Graphs}},
  author = {Yuanming Luo and Hao Hu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.14135},
  eprint = {2610.14135},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.14135},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Reconstruction and Symmetry of Two-Token Graphs
AU  - Yuanming Luo
AU  - Hao Hu
PY  - 2026
DA  - 2026/10/09
PB  - arXiv
DO  - 10.48550/arxiv.2610.14135
UR  - https://arxiv.org/abs/2610.14135
AB  - We present a proof of the two-token graph reconstruction conjecture. Every finite simple graph G,H of order at least three, F_2(G) ≅ F_2(H) if and only if G ≅ H. We also classify the automorphism groups of two-token graphs whose connected roots have order at least five. Combining these results, we show that, for connected graphs G,H of order at least five, every isomorphism ϕ:F_2(G)→ F_2(H) admits a factorization ϕ=η∘σ^(2), where σ^(2) is induced by a graph isomorphism σ:G→ H, and η∈ Aut(F_2(H)) is a product of twin-cut switches or Cartesian exchanges.
ER  -