Graphs and Combinatorics Дискретная математика и комбинаторика

On the Automorphisms of Token Graphs Generated by 2-cuts with the Same Neighbours

Ruy Fabila-Monroy, Sergio Gerardo Gómez-Galicia, Daniel Gregorio-Longino, Teresa I. Hoekstra-Mendoza, Ana Trujillo-Negrete
Springer Nature · 2025-12-03 · DOI 10.1007/s00373-025-03001-9

Аннотация

Abstract Let G be a connected graph on n vertices and $$1 \le k \le n-1$$ 1 ≤ k ≤ n - 1 an integer. The k -token graph of G is the graph $$F_k(G)$$ F k ( G ) , whose vertices are all the k -subsets of vertices of G , two of which are adjacent whenever their symmetric difference is an edge of G . Every automorphism of G induces an automorphism of $$F_k(G)$$ F k ( G ) in a natural way. Suppose that $$S:=\{x,y\}$$ S : = { x , y } is a cut set of G , such that x and y have the same neighbours in $$G\setminus \{x,y\}$$ G \ { x , y } . In this paper, we show that there exists a large number of automorphisms of $$F_k(G)$$ F k ( G ) defined by S that are not induced by automorphisms of G . We also describe the group produced by all such 2-cuts of G .

Читать у издателя →