Token-sliding realizability for complements, Cartesian-products, and grid graph families

Abstract

For an integer $k\ge 0$ and a graph $G$, the \emph{token-sliding reconfiguration graph ${\mathsf{TS}}_k(G)$} has the independent $k$-sets of $G$ as vertices. Two vertices are adjacent if one token can slide along an edge of $G$ and the resulting $k$-set is still independent. We study the following realizability problem: for fixed $k\ge 2$, which graphs are isomorphic to ${\mathsf{TS}}_k(G)$ for some graph $G$? This inverse viewpoint asks which abstract state spaces can occur exactly under a local token rule. We give positive realizability results for the complement targets $\overline{K_n}$, $\overline{K_{m,n}}$, and $\overline{K_n-e}$, and we determine sharp cutoffs for complements of paths and cycles. We also prove a product formula for token-sliding graphs of disjoint unions and apply it to Cartesian products of complete graphs, paths, and cycles. For every grid $\hat{I}{“}_{m,n}=P_m\square P_n$ with $2\le m\le n$, we realize $\hat{I}{“}_{m,n}$ at token value $m+n-2$ and at every token value $k\ge 4$. At small token values, we prove that $C_4\square C_n$ is not a ${\mathsf{TS}}_2$-graph for $n\ge 4$, classify ladders $\hat{I}{“}_{2,n}$, and settle the first non-ladder grid: for $k\ge 2$, $\hat{I}{“}_{3,3}$ is realizable if and only if $k\ge 4$.

29 pages, 9 figures