Downloads: 123
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
arXiv.2203.16861.pdf | 853.87 kB | Adobe PDF | View/Open |
Title: | On Reconfiguration Graphs of Independent Sets under Token Sliding |
Authors: | AVIS, David HOANG, Duc Anh |
Keywords: | Token sliding Reconfiguration graph Independent set Structure Realizability Geometric graph |
Issue Date: | 8-Dec-2022 |
Start page: | 1 |
End page: | 17 |
Abstract: | An independent set of a graph $G$ is a vertex subset $I$ such that there is no edge joining any two vertices in $I$. Imagine that a token is placed on each vertex of an independent set of $G$. The $mathsf{TS}$- ($mathsf{TS}_k$-) reconfiguration graph of $G$ takes all non-empty independent sets (of size $k$) as its nodes, where $k$ is some given positive integer. Two nodes are adjacent if one can be obtained from the other by sliding a token on some vertex to one of its unoccupied neighbors. This paper focuses on the structure and realizability of these reconfiguration graphs. More precisely, we study two main questions for a given graph $G$: (1) Whether the $mathsf{TS}_k$-reconfiguration graph of $G$ belongs to some graph class $mathcal{G}$ (including complete graphs, paths, cycles, complete bipartite graphs, connected split graphs, maximal outerplanar graphs, and complete graphs minus one edge) and (2) If $G$ satisfies some property $mathcal{P}$ (including $s$-partitedness, planarity, Eulerianity, girth, and the clique's size), whether the corresponding $mathsf{TS}$- ($mathsf{TS}_k$-) reconfiguration graph of $G$ also satisfies $mathcal{P}$, and vice versa. Additionally, we give a decomposition result for splitting a $mathsf{TS}_k$-reconfiguration graph into smaller pieces. |
Rights: | This paper is made available under the CC BY-SA 4.0 license. |
URI: | http://hdl.handle.net/2433/277778 |
DOI(Published Version): | 10.48550/arXiv.2203.16861 |
Appears in Collections: | Preprint |

This item is licensed under a Creative Commons License