Graphs


1 Reconfiguration Graph of Independent Sets under Token Sliding

This section contains some supplement data for [1].

1.1 Definitions

An independent set I of a graph G is a subset of vertices of G where any two members u,vI, there is no edge of G connecting u and v. The reconfiguration graph of independent sets of G under Token Sliding, denoted by 𝖳𝖲(G), takes all independent sets of G as its nodes (vertices). Two nodes I,J of 𝖳𝖲(G) are adjacent if there are two vertices u,v such that IJ={u}, JI={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=𝖳𝖲(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 𝖳𝖲(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.

n G 𝖳𝖲(G)
connected planar tree path cycle
G 𝖳𝖲(G) G 𝖳𝖲(G) G 𝖳𝖲(G) G 𝖳𝖲(G)
n=6 99 99 6 6 1 1 1 1 planar
0 0 0 0 0 0 0 0 nonplanar
n=7 584 584 11 11 1 1 0 0 planar
62 62 0 0 0 0 1 1 nonplanar
n=8 3145 3145 16 16 1 1 0 0 planar
2829 2829 7 7 0 0 1 1 nonplanar
n=9 7863 7863 12 12 0 0 0 0 planar
64022 64022 35 35 1 1 1 1 nonplanar

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{6,7,8,9} vertices.

References

  • [1] D. Avis and D. A. Hoang (2022) On Reconfiguration Graph of Independent Sets under Token Sliding. arXiv preprint. External Links: 2203.16861 Cited by: §1.