论文标题
关于令牌滑动下独立集的重新配置图
On Reconfiguration Graphs of Independent Sets under Token Sliding
论文作者
论文摘要
一组独立的图形$ g $是一个顶点子集$ i $，因此没有边缘加入$ i $的两个顶点。想象一下，将一个令牌放在一个独立的$ g $的顶点上。 $ \ mathsf {ts} $ - （$ \ mathsf {ts} _k $ - ）$ g $的重新配置图将所有非空的独立集（尺寸$ k $）作为节点，其中$ k $有一些给定的正整数。如果一个节点可以通过在某个顶点上滑动到其一个无人居住的邻居之一，则两个节点相邻。本文着重于这些重新配置图的结构和可实现性。更确切地说，我们研究给定图形$ g $的两个主要问题：（1）$ \ mathsf {ts} _K $ -ReconFiguration $ g $的图形属于某些图形类别$ \ Mathcal {g g} $ （2）如果$ g $满足某些属性$ \ MATHCAL {p} $（包括$ s $ partited，平面性，欧拉特尼，吉尔特和集团的大小），是否相应的$ \ shssf {ts} $ - （ $ \ mathcal {p} $，反之亦然。此外，我们给出一个分解结果，以将$ \ mathsf {ts} _K $ -Reconfiguration图分解为较小的零件。
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.
