Token-sliding realizability for complements, Cartesian-products, and grid graph families
Duc A. Hoang · 2026
Read Token-sliding realizability for complements, Cartesian-products, and grid graph families by Duc A. Hoang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-03765.txt.
Description
Hoang asks which graphs can arise as token-sliding reconfiguration graphs. Tokens sit on independent sets of a graph, one per vertex. A move slides a token along an edge while the set stays independent. The reconfiguration graph links all such k-token states. The realizability problem inverts the view: which abstract graphs occur this way for some base graph? The token count k is fixed at two or more.
Positive results cover complements of complete graphs and complete bipartite graphs. A complement missing one edge is also realizable. Sharp cutoffs are found for complements of paths and cycles. A product formula for disjoint unions extends the results to Cartesian products. Every grid is realizable at a high token value and at all values from four up. Small cases are classified: one four-cycle product fails at k equals two, and the 3-by-3 grid needs k of at least four.
Catalog record
| CREATOR | Duc A. Hoang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 103 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.03765