Let G) be a connected graph with n≥ 5 vertices and prime factor decomposition G=G_1 square…square G_r, where r>1. Let psi be the homomorphism from operatornameAut(G) to operatornameAut(Z_2^[r-1]) defined by the induced permutation of the prime factors. Automorphism-group characterization. The automorphism group of the k-token graph of G should satisfy operatornameAut(F_k(G))simeq Z_2^[r-1]rtimes_psioperatornameAut(G) & textrmif k=2, operatornameAut(G)×Z_2 & textrmif k=n/2, operatornameAut(G) & textrmotherwise. This gives the complete automorphism group of the token graphs in the stated range, extending the preceding lower-bound result for F_2(G). The parser supplies no evidence that the characterization has been proved or disproved, so its status remains open.

The automorphism-group characterization for token graphs of connected Cartesian products

About 3 years old · traced to 2023

Let $G$ ) be a connected graph with $n\geq 5$ vertices and prime factor decomposition

G=G_1\square\cdots\square G_r,

where $r>1$ . Let $\psi$ be the homomorphism from $\operatorname{Aut}(G)$ to $\operatorname{Aut}(\mathbb{Z}_2^{[r-1]})$ defined by the induced permutation of the prime factors. Automorphism-group characterization. The automorphism group of the $k$ -token graph of $G$ should satisfy

\operatorname{Aut}(F_k(G))\simeq \begin{cases} \mathbb{Z}_2^{[r-1]}\rtimes_{\psi}\operatorname{Aut}(G) & \textrm{if } k=2,\\ \operatorname{Aut}(G)\times\mathbb{Z}_2 & \textrm{if } k=n/2,\\ \operatorname{Aut}(G) & \textrm{otherwise.} \end{cases}

This gives the complete automorphism group of the token graphs in the stated range, extending the preceding lower-bound result for $F_2(G)$ . The parser supplies no evidence that the characterization has been proved or disproved, so its status remains open.

References

Primary source

Ruy Fabila-Monroy and Ana Laura Trujillo-Negrete, “On the Automorphism Group of Token Graphs of Complete Bipartite Graphs”, arXiv:2302.07914 (2025).

Posted 1 month ago · edited 2 weeks ago

Progress summary

Refreshed 2 weeks ago

Open

No proof or counterexample has been publicly reported, so the proposed complete description remains open.

A May 12, 2023 preprint states this as Conjecture 1.1 for connected graphs with $n \ge 5$ and multiple Cartesian prime factors. It predicts the full automorphism group of every token graph, with exceptional cases at $k=2$ and $k=n/2$ .

Known results

Zhang, Zhou, Lee, Li, and Xie (2023) proved the lower bound $\mathbb{Z}_2^{[r-1]} \rtimes_{\psi} \operatorname{Aut}(G) \leq \operatorname{Aut}(F_2(G))$ .
They proved equality for the cube $Q_r$ when $r \ge 3$ .
Complete descriptions are known for selected families, including complete bipartite graphs and connected $(C_4,\mathrm{diamond})$ -free graphs.

2024 lower-bound update

A 2024 paper extended subgroup constructions to Cartesian products of prime graphs and obtained further automorphisms of $F_k(G)$ . It neither proves nor refutes the proposed three-case characterization.

Current status (as of September 2026): Lower bounds and special cases are established, but the full automorphism-group characterization remains open.

Sources

No solutions have been posted yet.