On the Automorphisms of Token Graphs Generated by $2$-cuts with the Same Neighbours
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911981831716864 |
|---|---|
| author | Fabila-Monroy, Ruy Gómez-Galicia, Sergio Gerardo Gregorio-Longino, Daniel Hoekstra-Mendoza, Teresa I. Trujillo-Negrete, Ana |
| author_facet | Fabila-Monroy, Ruy Gómez-Galicia, Sergio Gerardo Gregorio-Longino, Daniel Hoekstra-Mendoza, Teresa I. Trujillo-Negrete, Ana |
| contents | Let $G$ be a connected graph on $n$ vertices and $1 \le k \le n-1$ an integer. The $k$-token graph of $G$ is the graph $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)$ in a natural way. Suppose that $S:=\{x,y\}$ is a cut set of $G$, such that $x$ and $y$ have the same neighbours in $G\setminus \{x,y\}$. In this paper we show that there exist a large number of automorphisms of $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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_04059 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Automorphisms of Token Graphs Generated by $2$-cuts with the Same Neighbours Fabila-Monroy, Ruy Gómez-Galicia, Sergio Gerardo Gregorio-Longino, Daniel Hoekstra-Mendoza, Teresa I. Trujillo-Negrete, Ana Combinatorics Let $G$ be a connected graph on $n$ vertices and $1 \le k \le n-1$ an integer. The $k$-token graph of $G$ is the graph $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)$ in a natural way. Suppose that $S:=\{x,y\}$ is a cut set of $G$, such that $x$ and $y$ have the same neighbours in $G\setminus \{x,y\}$. In this paper we show that there exist a large number of automorphisms of $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$. |
| title | On the Automorphisms of Token Graphs Generated by $2$-cuts with the Same Neighbours |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2408.04059 |