On the automorphism group of token graphs of Hamming graphs

Abstract

Esta tesis explora el grupo de automorfismos de los grafos de tokens de ciertos grafos específicos. Dado un grafo $G$ de orden $n$ y un entero $k$ con $1\leq k \leq n-1$, el \textit{grafo de $k$-tokens} de $G$, denotado por $F_k(G)$, es el grafo cuyos vértices son todos los subconjuntos de $k$ vértices de $G$, donde dos de tales subconjuntos son adyacentes si y solo si su diferencia simétrica es un par de vértices adyacentes en $G$. Los vértices de $F_k(G)$ representan configuraciones en las que se colocan $k$ tokens indistinguibles en vértices distintos de $G$. Dos configuraciones son adyacentes si se puede obtener una de la otra moviendo un solo token a lo largo de una arista hacia un vértice desocupado. Los grafos de tokens se han estudiado desde al menos la década de 1980, bajo diferentes nombres y por diferentes autores. Estos grafos tienen varias aplicaciones en Física y Teoría de Códigos.

Nos centramos en el grupo de automorfismos de los grafos de tokens cuando el grafo subyacente es un producto cartesiano de grafos completos. Con respecto a este problema, ya se pueden encontrar varios resultados en la literatura. Entre ellos, en ~\cite{Ibarra2023} se muestra que \begin{equation} \label{inequalities2} \aut(F_k(G))\geq \begin{cases} \aut(G) & \textrm{si $k\ne n/2$,} \\ \mathbb{Z}_2\times \aut(G) & \textrm{si $k= n/2$. } \end{cases} \end{equation}

Un problema natural es estudiar una caracterización de los grafos y valores de $k$ para los cuales los grafos de $k$-tokens satisfacen~\eqref{inequalities2} como desigualdades estrictas o igualdades.

Hasta donde sabemos, el grupo de automorfismos de los grafos de $k$-tokens de los grafos de Hamming solo se ha estudiado para \( k=2 \) ~\cite{ZHANG2023127872}. Por lo tanto, esta tesis tiene como objetivo extender los resultados con el grupo de automorfismos de los grafos de $k$-tokens de los grafos de Hamming cuando $k \geq 3$. En particular, establecemos el grupo de automorfismos de:

\begin{itemize} \item $F_k(K_n\square K_2)$ para $n\ge k\ge 3$, \item $F_k(K_n\square K_m)$ para $n\ge m$ y $n\ge k\ge 3$, y, \item $F_k(K_{n_1}\square K_{n_2}\square ...\square K_{n_m})$ para $m>2$ y $n_1\geq n_2 \geq ... \geq n_m \geq 2$. \end{itemize}

This thesis explores the automorphism group of token graphs for certain specific graphs. Given a graph G of order n and an integer k with 1 ≤ k ≤ n − 1, the k-token graph of G, denoted by Fk(G), is the graph whose vertices are all the subsets of k vertices of G, where two such subsets are adjacent if and only if their symmetric difference is a pair of adjacent vertices in G. The vertices of Fk(G) represent configurations where k indistinguishable tokens are placed on distinct vertices of G. Two configurations are adjacent if one can be obtained from the other by moving a single token along an edge to an empty vertex. Token graphs have been studied since at least the 1980s, under different names and by different authors. These graphs have several applications in Physics and Coding Theory. We focus on the automorphism group of token graphs when the underlying graph is a Cartesian product of complete graphs. Regarding this problem, several results can already be found in the literature. Among them, in [IR23] it is shown that Aut(Fk(G)) ≥ ( Aut(G) if k ̸= n/2, Z2 × Aut(G) if k = n/2. (2) A natural problem is to study a characterization of the graphs and values of k for which the token graphs of k satisfy (2) as strict inequalities or equalities. As far as we know, the automorphism group of token graphs of k for Hamming graphs has only been studied for k = 2 [Zha+23]. Therefore, this thesis aims to extend the results with the automorphism group of token graphs of k for Hamming graphs when k ≥ 3. In particular, we establish the automorphism group of: • Fk(Kn□K2) for n ≥ k ≥ 3, • Fk(Kn□Km) for n ≥ m and n ≥ k ≥ 3, and, • Fk(Kn1□Kn2□ . . . □Knm) for m > 2 and n1 ≥ n2 ≥ · · · ≥ nm ≥ 2.