Contents
1 Reconfiguration Graph of Independent Sets under Token Sliding
This section contains some supplement data for [1].
1.1 Definitions
An independent set of a graph is a subset of vertices of where any two members , there is no edge of connecting and . The reconfiguration graph of independent sets of under Token Sliding, denoted by , takes all independent sets of as its nodes (vertices). Two nodes of are adjacent if there are two vertices such that , , and is an edge of .
1.2 Graph Data
-
•
The first line of the file contains the number of graphs, followed by a blank line.
-
•
For each graph , if is nonplanar for some graph , we provide data on a Kuratowski subgraph of , not the whole graph .
-
•
For each graph:
-
–
The first line contains the number of vertices .
-
–
Each of the next lines is of the form:
vertex: label
. Thevertex
is counted from to . If the graph is planar, the format isvertex: label: x y
, where and are the coordinates of the vertex in a planar layout of the graph. If the graph is for some graph , thelabel
is of the form[v1, v2, ..., vk]
, which represents a size- independent set of . -
–
The next 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 vertices.
References
- [1] (2022) On Reconfiguration Graph of Independent Sets under Token Sliding. arXiv preprint. External Links: 2203.16861 Cited by: §1.