Hamiltonicity of Token Graphs of some Join Graphs

Abstract

Let $G$ be a simple graph of order $n$ and let $k$ be an integer such that $1\le k\le n-1$. The $k$-token graph $G^{\{k\}}$ of $G$ is the graph whose vertices are the $k$-subsets of $V(G)$, where two vertices are adjacent in $G^{\{k\}}$ whenever their symmetric difference is a pair of adjacent vertices in $G$. In this paper we study the Hamiltonicity of the $k$-token graphs of some join graphs. As a consequence, we provide an infinite family of graphs (containing Hamiltonian and non-Hamiltonian graphs) for which their $k$-token graphs are Hamiltonian. Our result provides, to our knowledge, the first family of non-Hamiltonian graphs for which their $k$-token graphs are Hamiltonian, for $2<k<n-2$.

The results presented in this article generalize some results presented in arXiv:2007.00115. V2 is a revised version and some mistakes in our proofs were corrected