Automorphisms of Token Graphs That Send $4$-Cycles Generated by Two Edges to Cycles Generated by a $4$-Cycle and Two Tokens
Abstract
Let G be a connected graph. The k-token graph of G is the graph Fk(G) whose vertex set consists of all subsets of k vertices of G, where two of them are adjacent whenever their symmetric difference is an edge of G. Every automorphism of G induces one of Fk(G), as does complementation when k=|G|/2; automorphisms of this form are called \emph{induced}. Fabila-Monroy et al.\ (Graphs and Combinatorics 42, 2026) show that token graphs can have many non-induced automorphisms, arising from \emph{twin cuts}. These are cut sets {x,y} whose two vertices have the same neighbours (other than themselves) in G. These non-induced automorphisms send configurations with a prescribed number of tokens on each component of G∖ {x,y}, totalling k−1, and exactly one token on one vertex of {x,y}, to the configuration obtained by moving (\emph{flipping}) the token at {x,y} to the other vertex of {x,y}. These automorphisms send an induced $4$-cycle generated by moving two tokens on two disjoint edges to one generated by moving two tokens on a $4$-cycle; thus introducing what we call a \emph{twist}. We prove a partial converse: if an isomorphism φ: Fk(G)→ Fk'(G') sends some $4$-cycle generated by moving two tokens on two disjoint edges to one generated by moving two tokens on a $4$-cycle, then G and G' have twin cuts {x,y} and {x',y'}, respectively. We also show that any twist can be undone by composing φ with twin-cut flips.
Related
- On generalized k-token graphs with distinguishable tokens and a maximum capacity of s tokens per vertex
- On generalized token graphs with tokens of different colors
- Thinking in Tokens, Talking in Bits: A Practical Interface for Token Communication
- Linear maps preserving Kasparov cycles and the characterization of induced automorphisms
- Composing group automorphisms with colour-preserving automorphisms of Cayley graphs
BibTeX
@misc{fabilamonroy2026automorphisms,
title = {{Automorphisms of Token Graphs That Send $4$-Cycles Generated by Two Edges to Cycles Generated by a $4$-Cycle and Two Tokens}},
author = {Ruy Fabila-Monroy and Sergio Gerardo Gómez-Galicia and Ana Laura Trujillo-Negrete},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.25529},
eprint = {2609.25529},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.25529},
}
RIS
TY - UNPB
TI - Automorphisms of Token Graphs That Send $4$-Cycles Generated by Two Edges to Cycles Generated by a $4$-Cycle and Two Tokens
AU - Ruy Fabila-Monroy
AU - Sergio Gerardo Gómez-Galicia
AU - Ana Laura Trujillo-Negrete
PY - 2026
DA - 2026/09/22
PB - arXiv
DO - 10.48550/arxiv.2609.25529
UR - https://arxiv.org/abs/2609.25529
AB - Let G be a connected graph. The k-token graph of G is the graph F_k(G) whose vertex set consists of all subsets of k vertices of G, where two of them are adjacent whenever their symmetric difference is an edge of G. Every automorphism of G induces one of F_k(G), as does complementation when k=|G|/2; automorphisms of this form are called \emph{induced}. Fabila-Monroy et al.\ (Graphs and Combinatorics 42, 2026) show that token graphs can have many non-induced automorphisms, arising from \emph{twin cuts}. These are cut sets {x,y} whose two vertices have the same neighbours (other than themselves) in G. These non-induced automorphisms send configurations with a prescribed number of tokens on each component of G∖ {x,y}, totalling k−1, and exactly one token on one vertex of {x,y}, to the configuration obtained by moving (\emph{flipping}) the token at {x,y} to the other vertex of {x,y}. These automorphisms send an induced $4$-cycle generated by moving two tokens on two disjoint edges to one generated by moving two tokens on a $4$-cycle; thus introducing what we call a \emph{twist}. We prove a partial converse: if an isomorphism φ: F_k(G)→ F_k'(G') sends some $4$-cycle generated by moving two tokens on two disjoint edges to one generated by moving two tokens on a $4$-cycle, then G and G' have twin cuts {x,y} and {x',y'}, respectively. We also show that any twist can be undone by composing φ with twin-cut flips.
ER -