# Graphs

## 1 Reconfiguration Graph of Independent Sets under Token Sliding

### 1.1 Definitions

An independent set $I$ of a graph $G$ is a subset of vertices of $G$ where any two members $u,v\in I$, there is no edge of $G$ connecting $u$ and $v$. The reconfiguration graph of independent sets of $G$ under Token Sliding, denoted by $\mathsf{TS}(G)$, takes all independent sets of $G$ as its nodes (vertices). Two nodes $I,J$ of $\mathsf{TS}(G)$ are adjacent if there are two vertices $u,v$ such that $I\setminus J=\{u\}$, $J\setminus I=\{v\}$, and $uv$ is an edge of $G$.

### 1.2 Graph Data

• The first line of the file contains the number of graphs, followed by a blank line.

• For each graph $H$, if $H=\mathsf{TS}(G)$ is nonplanar for some graph $G$, we provide data on a Kuratowski subgraph of $H$, not the whole graph $H$.

• For each graph:

• The first line contains the number of vertices $n$.

• Each of the next $n$ lines is of the form: vertex: label. The vertex is counted from $0$ to $n-1$.

If the graph is planar, the format is vertex: label: x y, where $x$ and $y$ are the coordinates of the vertex in a planar layout of the graph.

If the graph is $\mathsf{TS}(G)$ for some graph $G$, the label is of the form [v1, v2, ..., vk], which represents a size-$k$ independent set of $G$.

• The next $n$ lines describe the corresponding adjacency matrix.

• The description ends by a blank line.

## History

• 2021/07/13: Add data on planarity/nonplanarity of reconfiguration graph of independent sets under Token Sliding, where the original input graph has $n\in\{6,7,8,9\}$ vertices.