On Reconfiguration Graph of Independent Sets under Token Sliding

Paper

Avis, Hoang - On Reconfiguration Graph of Independent Sets under Token Sliding

Setup

• Put a token on one vertex of every independent set of a given graph $G$.
• Tokens can slide to neighbours that are not occupied.
• Construct a new graph $G'$ in the following way: Two vertices are adjacent if we can slide one token to one of its adjacent vertices.
• This is called TS or TS$_k$ if we restrict ourselves to independent sets of size $k$.
• Questions:
  • Does TS$_k(G)$ belong to some graph class?
  • If $G$ satisfies some property, does $TS(G)$ also satisfy the property and vice versa?

Results

• TS_k($\bar G$) is a subgraph of the graph whose nodes are size $k$ cliques and two nodes are adjacent if they have exactly $k-1$ vertices in common.
• If $H$ is an induced subgraph of $G$ then TS$_k(H)$ is an induced subgraph of TS$_k(G)$ (but not the reverse).
• TS$(P_n)$ is planar for every $n\leq 8$ but non-planar otherwise (where $P_n$ is a planar graph on $n$ vertices),
• More similar results.