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

Abstract Let G be a connected graph on n vertices and $$1 \le k \le n-1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>≤</mml:mo> <mml:mi>k</mml:mi> <mml:mo>≤</mml:mo> <mml:mi>n</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> an integer. The k -token graph of G is the graph $$F_k(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>F</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , 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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>F</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> in a natural way. Suppose that $$S:=\{x,y\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>S</mml:mi> <mml:mo>:</mml:mo> <mml:mo>=</mml:mo> <mml:mo>{</mml:mo> <mml:mi>x</mml:mi> <mml:mo>,</mml:mo> <mml:mi>y</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> is a cut set of G , such that x and y have the same neighbours in $$G\setminus \{x,y\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>\</mml:mo> <mml:mo>{</mml:mo> <mml:mi>x</mml:mi> <mml:mo>,</mml:mo> <mml:mi>y</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> . In this paper, we show that there exists a large number of automorphisms of $$F_k(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>F</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> defined by S that are not induced by automorphisms of G . We also describe the group produced by all such 2-cuts of G .