Hamiltonicity of Token Graphs of some Join Graphs

DOI10.3390/SYM13061076MaRDI QIDQ6357673zbMATH OpenFDO

Authors Luis Enrique Adame, Luis Manuel Rivera, Ana Laura Trujillo-Negrete

Publication date 5 January 2021

Full work available at URL https://doi.org/10.3390/SYM13061076

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Graph operations (line graphs, products, etc.) (05C76)

Abstract: Let $G$ be a simple graph of order $n$ and let $k$ be an integer such that $1leqkleqn-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$.

This page was built for publication: Hamiltonicity of Token Graphs of some Join Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6357673)