Automorphisms of Token Graphs That Send -Cycles Generated by Two Edges to Cycles Generated by a -Cycle and Two Tokens
En palabras de los autores
Let be a connected graph. The -token graph of is the graph whose vertex set consists of all subsets of vertices of , where two of them are adjacent whenever their symmetric difference is an edge of . Every automorphism of induces one of , as does complementation when ; automorphisms of this form are called induced. Fabila-Monroy et al.\ (Graphs and Combinatorics 42, 2026) show that token graphs can have many non-induced automorphisms, arising from twin cuts. These are cut sets whose two vertices have the same neighbours (other than themselves) in . These non-induced automorphisms send configurations with a prescribed number of tokens on each component of , totalling , and exactly one token on one vertex of , to the configuration obtained by moving (flipping) the token at to the other vertex of . These automorphisms send an induced -cycle generated by moving two tokens on two disjoint edges to one generated by moving two tokens on a -cycle; thus introducing what we call a twist. We prove a partial converse: if an isomorphism sends some -cycle generated by moving two tokens on two disjoint edges to one generated by moving two tokens on a -cycle, then and have twin cuts and , respectively. We also show that any twist can be undone by composing with twin-cut flips.
Apareció: miércoles, 23 de septiembre. arXiv. Preprint, todavía sin revisión por pares.