Let G be a connected graph on n vertices and <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$1 \le k \le n-1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>≤</mo> <mi>k</mi> <mo>≤</mo> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> an integer. The k-token graph of G is the graph <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$F_k(G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>F</mi> <mi>k</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, 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 <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$F_k(G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>F</mi> <mi>k</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> in a natural way. Suppose that <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$S:=\{x,y\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>S</mi> <mo>:</mo> <mo>=</mo> <mo stretchy="false">{</mo> <mi>x</mi> <mo>,</mo> <mi>y</mi> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> is a cut set of G, such that x and y have the same neighbours in <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$G\setminus \{x,y\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo> <mo stretchy="false">{</mo> <mi>x</mi> <mo>,</mo> <mi>y</mi> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>. In this paper, we show that there exists a large number of automorphisms of <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$F_k(G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>F</mi> <mi>k</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> defined by S that are not induced by automorphisms of G. We also describe the group produced by all such 2-cuts of G.

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

期刊论文
出版模式：

开放获取
发表日期：

2025年12月3日

查看全文

Ruy Fabila-Monroy,
Sergio Gerardo Gómez-Galicia,
Daniel Gregorio-Longino,
Teresa I. Hoekstra-Mendoza,
Ana Trujillo-Negrete

摘要

Let G be a connected graph on n vertices and $1 \le k \le n-1$ $1 \leq k \leq 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.