AI summaryⓘ
The authors study a special kind of graph called the token-sliding reconfiguration graph, where each vertex represents a group of tokens placed on a graph without overlapping, and edges correspond to moving one token along an edge without overlap. They investigate which graphs can be exactly represented as token-sliding graphs for some original graph and a fixed number of tokens. Their work includes identifying specific graph types that appear as these token-sliding graphs, formulas for combining such graphs, and detailed results about small grid graphs and certain product graphs. They also find exact thresholds for when certain graphs can or cannot be realized as token-sliding graphs for given token numbers.
token-sliding reconfiguration graphindependent setgraph isomorphismreconfiguration problemCartesian product of graphsgrid graphcomplement graphdisjoint union of graphspaths and cyclesgraph realizability
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 $Γ_{m,n}=P_m\square P_n$ with $2\le m\le n$, we realize $Γ_{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 $Γ_{2,n}$, and settle the first non-ladder grid: for $k\ge 2$, $Γ_{3,3}$ is realizable if and only if $k\ge 4$.