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

CREATORDuc A. Hoang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE103 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.03765

Browse the full library · About the Tower of Babel